Closeness Centrality¶

Algorithm introduction¶

Closeness centrality evaluates how near a node is to all other reachable nodes via shortest path distances.

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

For more information, see Closeness Centrality.

Data model¶

To implement the Closeness 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.

Procedure implementation ¶

To compute Closeness Centrality results, a procedure is created.

For more information about the procedure, see Procedure implementation. 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	Active set for the current BFS frontier.
`source_ids`	Global SumAgg aggregator value variable	List of all node IDs used as BFS sources.
`has_next`	Primitive value variable	Whether the BFS frontier has nodes to expand.
`vertex_cnt`	Global SumAgg aggregator value variable	Total number of nodes in the graph.
`dist_sum`	Global SumAgg aggregator value variable	Sum of shortest-path distances from the current source.
`reach_cnt`	Global SumAgg aggregator value variable	Count of nodes reachable from the current source.
`inf`	Primitive value variable	Infinity sentinel for unreachable distances.
`source_id`	Primitive value variable	Current source node ID.
`src_idx`	Primitive value variable	Index into source_ids for outer-loop progress.
`level`	Primitive value variable	Current BFS hop depth.
`score`	Node-attached SumAgg aggregator value variable	Per-node closeness centrality score.
`dist`	Node-attached SumAgg aggregator value variable	Per-node shortest-path distance from the current source.
`result_table`	Table variable	Output table storing (vertex_id, score) pairs.

The following steps outline the logic of the procedure:

Collect all node IDs into source_ids and count vertex_cnt.
For each source node, run a BFS to compute dist_sum (total distances) and reach_cnt (reachable nodes).
Compute each source node's closeness score as reach_cnt² / (vertex_cnt × dist_sum).
Return (vertex_id, score) for all nodes, sorted by score descending.

Steps¶

Run the following code blocks in order in the NebulaGraph Studio CONSOLE. For first-time setup, follow Prepare algorithm sample data to check where to run commands and how the directory is mounted.

1. Prepare graph data ¶

Create a graph type that matches your data model.

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

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

closeness_centrality_node.csv: Node data.
closeness_centrality_edge.csv: Edge data.

Preview the CSV files

closeness_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

closeness_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

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

CREATE TEMPORARY GRAPH IF NOT EXISTS #closeness_centrality_graph TYPED closeness_centrality_graph_type

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

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

'''
USE #closeness_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 before continuing.

2. Create a procedure ¶

Create a procedure to implement the Closeness Centrality algorithm. For more information about the procedure, see Procedure implementation.

'''
CREATE OR REPLACE PROCEDURE closeness_centrality()
RETURNS (vertex_id INT64, score DOUBLE)
COMMENT "Compute classic unweighted closeness centrality for all vertices on an undirected graph, 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 vertex_cnt SumAgg<INT64> = 0
  VALUE dist_sum SumAgg<INT64> = 0
  VALUE reach_cnt SumAgg<INT64> = 0
  VALUE inf INT64 = 1000000000
  VALUE source_id INT64 = 0
  VALUE src_idx INT64 = 0
  VALUE level INT64 = 0

  NODE VALUE score SumAgg<DOUBLE> = 0.0
  NODE VALUE dist MinAgg<INT64> = 1000000000

  TABLE result_table TYPED TABLE {vertex_id INT64, score DOUBLE}

  MATCH (n)
  PER NODE (n) {
    SET n.@score = 0.0
    SET n.@dist = inf
    SET @source_ids += n.id
    SET @vertex_cnt += 1
  }

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

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

    MATCH (s)
    WHERE s.id = source_id
    PER NODE (s) {
      SET s.@dist = 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 {
        MATCH (v)
        WHERE v IN frontier
        PER NODE (v) {
          SET v.@dist = level
          SET @dist_sum += level
          SET @reach_cnt += 1
        }
      }
    }

    MATCH (s)
    WHERE s.id = source_id
    PER NODE (s) {
      IF @dist_sum > 0 AND @reach_cnt = @vertex_cnt - 1 THEN {
        SET s.@score = CAST(@reach_cnt AS DOUBLE) / CAST(@dist_sum AS DOUBLE)
      }
      ELSE {
        SET s.@score = 0.0
      }
    }
  }

  MATCH (n)
  PER NODE (n) {
    EXPORT n.id, n.@score 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 closeness centrality scores for the nodes.

USE #closeness_centrality_graph CALL closeness_centrality() RETURN vertex_id, score

Returns:

Expand to view results

+-----------+---------------------+
| vertex_id | score               |
+-----------+---------------------+
| 14        | 0.4791666666666667  |
| 10        | 0.46938775510204084 |
| 12        | 0.46938775510204084 |
| 15        | 0.4423076923076923  |
| 11        | 0.4339622641509434  |
| 9         | 0.42592592592592593 |
| 16        | 0.42592592592592593 |
| 18        | 0.42592592592592593 |
| 8         | 0.41818181818181815 |
| 13        | 0.41818181818181815 |
| 6         | 0.40350877192982454 |
| 17        | 0.39655172413793105 |
| 19        | 0.3770491803278688  |
| 7         | 0.3709677419354839  |
| 5         | 0.3484848484848485  |
| 4         | 0.34328358208955223 |
| 21        | 0.34328358208955223 |
| 22        | 0.32857142857142857 |
| 2         | 0.3150684931506849  |
| 3         | 0.3150684931506849  |
| 20        | 0.3150684931506849  |
| 1         | 0.27710843373493976 |
| 24        | 0.26744186046511625 |
| 23        | 0.26436781609195403 |
+-----------+---------------------+

Save results to a file or graph

To save the returned results as CSV files or write them to a graph, see EXPORT. Match the exported fields to the returned columns and target properties.

Closeness Centrality¶

Algorithm introduction¶

Data model¶

Procedure implementation¶

Steps¶

1. Prepare graph data¶

2. Create a procedure¶

3. Call your procedure¶

Procedure implementation ¶

1. Prepare graph data ¶

2. Create a procedure ¶

3. Call your procedure ¶