Source: https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/betweenness_centrality/
Documentation version: v5.3.2

# Betweenness Centrality

## Algorithm introduction

Betweenness centrality quantifies how often a node lies on shortest paths between other node pairs.

Compute classic unweighted betweenness centrality for all nodes on an undirected graph via the Brandes algorithm, using node property id as the identifier and treating shortest paths by hop count.

For more information, see [Betweenness Centrality](https://en.wikipedia.org/wiki/Betweenness_centrality).

## Data model

To implement the Betweenness Centrality algorithm in GQL, the following data model is used to create a graph type:

- Entities are represented by nodes of type `Node`, with properties `id` and `rating`.
- Relationships are represented by edges of type `Link`, with property `weight`.

For the complete definition of the graph type, see [Prepare graph data](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/betweenness_centrality/#1_prepare_graph_data).

## Procedure implementation[]()

To compute Betweenness Centrality results, a [procedure](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/procedures/create/) is created.

For more information about the procedure, see [Procedure implementation](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/betweenness_centrality/#procedure_implement). The following section describes the key components of the procedure and how it works.

The procedure takes the following input parameters:

- This procedure does not require input parameters.

Additionally, the following variables are defined within the procedure:

 | Variable name | Variable type | Description
 | `frontier` | [Primitive value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/value-variable/) | Active set holding the current BFS frontier nodes.
 | `source_ids` | Global [SumAgg aggregator value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | List of all node IDs used as BFS sources.
 | `has_next` | [Primitive value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/value-variable/) | Whether the BFS frontier is non-empty for the current source.
 | `inf` | [Primitive value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/value-variable/) | Infinity sentinel for uninitialized distances.
 | `source_id` | [Primitive value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/value-variable/) | Current source node ID in the outer BFS loop.
 | `src_idx` | [Primitive value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/value-variable/) | Index into source_ids for outer-loop progress.
 | `level` | [Primitive value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/value-variable/) | Current BFS hop depth from the active source.
 | `max_level` | [Primitive value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/value-variable/) | Maximum BFS depth reached for the current source.
 | `rev_level` | [Primitive value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/value-variable/) | Reverse traversal level during back-propagation.
 | `bc` | Node-attached [SumAgg aggregator value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | Per-node accumulated betweenness centrality score.
 | `dist` | Node-attached [SumAgg aggregator value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | Per-node shortest-path hop distance from the current source.
 | `sigma` | Node-attached [SumAgg aggregator value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | Per-node count of shortest paths from the current source.
 | `delta` | Node-attached [SumAgg aggregator value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | Per-node dependency score accumulated during back-propagation.
 | `result_table` | [Table variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/table-variable/) | Output table storing (vertex_id, score) pairs.

The following steps outline the logic of the procedure:

1. Collect all node IDs into `source_ids` and initialize per-node `dist`, `sigma`, and `delta`.
2. For each source node, run a BFS to compute shortest-path hop counts (`dist`) and path counts (`sigma`).
3. Back-propagate dependency scores (`delta`) from the deepest BFS level back to the source, accumulating each node's contribution into `bc`.
4. Return each node's accumulated betweenness score (`vertex_id`, `score`), sorted descending.

## Steps

Run the following code blocks in order in the NebulaGraph Studio CONSOLE. For first-time setup, follow [Prepare algorithm sample data](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/prepare-data/) to check where to run commands and how the directory is mounted.

### 1. Prepare graph data[]()

1. 

Create a graph type that matches your data model.

````
'''
CREATE GRAPH TYPE IF NOT EXISTS betweenness_centrality_graph_type AS {
    NODE Node (LABEL Node {id INT PRIMARY KEY, rating INT}),
    EDGE Link (Node)-[LABEL Link {weight INT, MULTIEDGE KEY()}]->(Node)
}
'''

````

2. 

Download these CSV files and save them with their original names in `examples/algorithms/betweenness_centrality/` under your deployment directory:

  - [betweenness_centrality_node.csv](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/files/betweenness_centrality/betweenness_centrality_node.csv): Node data.
  - [betweenness_centrality_edge.csv](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/files/betweenness_centrality/betweenness_centrality_edge.csv): Edge data.

Preview the CSV files

betweenness_centrality_node.csv

````
id,rating
1,0
2,2
3,1
4,0
5,0
6,2
7,1
8,2
9,0
10,1
11,0
12,2
13,1
14,1
15,0
16,2
17,0
18,1
19,2
20,0
21,2
22,1
23,0
24,1

````

betweenness_centrality_edge.csv

````
src_id,dst_id,weight
1,2,4
1,3,2
1,4,7
1,5,9
2,3,1
2,4,6
2,5,5
2,6,2
3,4,3
3,5,4
3,6,8
4,6,2
4,7,6
4,8,5
5,6,4
5,8,7
5,9,6
6,8,1
6,9,5
6,10,6
7,9,2
7,10,9
8,9,3
8,11,6
8,12,4
9,10,4
9,12,7
9,13,2
10,12,1
10,13,8
10,14,4
11,12,2
11,14,5
11,15,7
12,14,3
12,15,6
12,16,5
13,15,2
13,16,7
14,15,4
14,17,8
14,18,2
15,16,1
15,18,5
15,19,3
16,18,3
16,19,6
17,18,2
17,20,7
17,21,5
18,19,4
18,21,9
18,22,6
19,21,1
19,22,5
20,21,3
20,23,6
20,24,8
21,22,2
21,23,4
21,24,7
22,24,4
23,24,1

````

3. 

Create a temporary graph based on the graph type and load the data files into the temporary graph.

````
CREATE TEMPORARY GRAPH IF NOT EXISTS #betweenness_centrality_graph TYPED betweenness_centrality_graph_type

````

````
'''
USE #betweenness_centrality_graph IMPORT INTO GRAPH {
      NODE (v@Node {id: id, rating: rating}) FROM DATAFILE {
          PATH: "file:///examples/algorithms/betweenness_centrality/betweenness_centrality_node.csv",
          FORMAT: "CSV",
          DELIMITER: ','
      },
      EDGE (id: src_id)-[e@Link {weight: weight}]->(id: dst_id) FROM DATAFILE {
          PATH: "file:///examples/algorithms/betweenness_centrality/betweenness_centrality_edge.csv",
          FORMAT: "CSV",
          DELIMITER: ','
      }
  }
'''

````

After the import succeeds, run this query in the console to check the node count:

````
'''
USE #betweenness_centrality_graph
MATCH (n)
RETURN count(n) AS node_count
'''

````

The expected `node_count` is `24`. If it differs, [check the files and import results](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/prepare-data/#troubleshooting) before continuing.

### 2. Create a procedure[]()

Create a procedure to implement the Betweenness Centrality algorithm. For more information about the procedure, see [Procedure implementation](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/betweenness_centrality/#procedure_implement). 

````
'''
CREATE OR REPLACE PROCEDURE betweenness_centrality()
RETURNS (vertex_id INT64, score DOUBLE)
COMMENT "Compute classic unweighted betweenness centrality for all vertices on an undirected graph via the Brandes algorithm, using vertex property id as the identifier and treating shortest paths by hop count."
AS {
  VALUE frontier ACTIVE_SET

  VALUE source_ids ListAgg<INT64>
  VALUE has_next OrAgg = false
  VALUE inf INT64 = 1000000000
  VALUE source_id INT64 = 0
  VALUE src_idx INT64 = 0
  VALUE level INT64 = 0
  VALUE max_level INT64 = 0
  VALUE rev_level INT64 = 0

  NODE VALUE bc SumAgg<DOUBLE> = 0.0
  NODE VALUE dist MinAgg<INT64> = 1000000000
  NODE VALUE sigma SumAgg<DOUBLE> = 0.0
  NODE VALUE delta SumAgg<DOUBLE> = 0.0

  TABLE result_table TYPED TABLE {vertex_id INT64, score DOUBLE}

  MATCH (n)
  PER NODE (n) {
    SET n.@bc = 0.0
    SET @source_ids += n.id
  }

  WHILE src_idx < @source_ids.size() THEN {
    SET source_id = @source_ids[src_idx]
    SET src_idx = src_idx + 1
    SET level = 0
    SET max_level = 0

    MATCH (n)
    PER NODE (n) {
      SET n.@dist = inf
      SET n.@sigma = 0.0
      SET n.@delta = 0.0
    }

    MATCH (s)
    WHERE s.id = source_id
    PER NODE (s) {
      SET s.@dist = 0
      SET s.@sigma = 1.0
      SET s.@delta = 0.0
    }
    FINALLY {
      SET frontier = s
    }

    SET @has_next = true

    WHILE @has_next = true THEN {
      SET @has_next = false
      SET level = level + 1

      MATCH (u)-[e]-(v)
      WHERE u IN frontier AND v.@dist = inf
      PER PATH {
        SET @has_next += true
      }
      FINALLY {
        SET frontier = v
      }

      IF @has_next = true THEN {
        SET max_level = level

        MATCH (v)
        WHERE v IN frontier
        PER NODE (v) {
          SET v.@dist = level
        }

        MATCH (v)-[e]-(u)
        WHERE v IN frontier AND u.@dist = level - 1
        PER PATH {
          SET v.@sigma += u.@sigma
        }
      }
    }

    SET rev_level = max_level

    WHILE rev_level > 0 THEN {
      MATCH (v)-[e]-(w)
      WHERE v.@dist = rev_level - 1 AND w.@dist = rev_level
      PER PATH {
        VALUE contrib DOUBLE = 0.0

        IF w.@sigma > 0.0 THEN {
          SET contrib = (v.@sigma / w.@sigma) * (1.0 + w.@delta)
          SET v.@delta += contrib
        }
      }

      MATCH (w)
      WHERE w.@dist = rev_level AND w.id <> source_id
      PER NODE (w) {
        SET w.@bc += w.@delta
      }

      SET rev_level = rev_level - 1
    }
  }

  MATCH (n)
  PER NODE (n) {
    EXPORT n.id, n.@bc / 2.0 INTO result_table
  }

  FOR r IN result_table
  RETURN r.vertex_id AS vertex_id, r.score AS score
  ORDER BY score DESC, vertex_id ASC
}
'''

````

### 3. Call your procedure[]()

Compute betweenness centrality scores for the nodes.

````
USE #betweenness_centrality_graph CALL betweenness_centrality() RETURN vertex_id, score

````

Returns:

Expand to view results

````
+-----------+--------------------+
| vertex_id | score              |
+-----------+--------------------+
| 14        | 67.8918657967101   |
| 10        | 51.75309772968774  |
| 18        | 40.30392916544371  |
| 12        | 37.370764716983835 |
| 6         | 33.38757193543222  |
| 8         | 32.13354984875291  |
| 17        | 30.42103303694065  |
| 21        | 29.912102529148715 |
| 15        | 26.875354636179623 |
| 9         | 24.913164244339967 |
| 5         | 16.162075382607817 |
| 16        | 15.65169579580913  |
| 19        | 14.87225072961119  |
| 11        | 12.14105197018898  |
| 4         | 12.043896472711737 |
| 13        | 11.120121682305985 |
| 22        | 6.730357142857143  |
| 20        | 6.524206994660801  |
| 7         | 3.3496843489235455 |
| 2         | 1.1211129203521168 |
| 3         | 1.1211129203521168 |
| 24        | 1.0                |
| 1         | 0.2                |
| 23        | 0.0                |
+-----------+--------------------+

````

Save results to a file or graph

To save the returned results as CSV files or write them to a graph, see [EXPORT](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/in-out/export/). Match the exported fields to the returned columns and target properties.