betweenness_centrality

Centrality analysis provides information about the node’s importance for an information flow or connectivity of the network. Betweenness centrality is one of the most used centrality metrics. Betweenness centrality measures the extent to which a node lies on paths between other nodes in the graph. Thus, nodes with high betweenness may have considerable influence within a network under their control over information passing between others. The calculation of betweenness centrality is not standardized, and there are many ways to solve it. It is defined as the number of shortest paths in the graph that passes through the node divided by the total number of shortest paths. The implemented algorithm is described in the paper "A Faster Algorithm for Betweenness Centrality" ¹.

¹ A Faster Algorithm for Betweenness Centrality, Ulrik Brandes

Trait	Value
Module type	algorithm
Implementation	C++
Graph direction	directed/undirected
Edge weights	unweighted
Parallelism	parallel

Procedures

info

If you want to execute this algorithm on graph projections, subgraphs or portions of the graph, be sure to check out the guide on How to run a MAGE module on subgraphs.

get(directed, normalized, threads)

Input:

• directed: boolean (default=True) ➡ If False the direction of the edges is ignored.
• normalized: boolean (default=True) ➡ If True the betweenness values are normalized by 2/((n-1)(n-2)) for graphs, and 1/((n-1)(n-2)) for directed graphs where n is the number of nodes.
• threads: integer (default=number of concurrent threads supported by the implementation) ➡ The number of threads used to calculate betweenness centrality.

Output:

• betweenness_centrality: float ➡ Value of betweenness for a given node.

• node: Vertex ➡ Graph vertex for betweenness calculation.

Usage:

CALL betweenness_centrality.get()
YIELD node, betweenness_centrality;

Example

Step 1: Input graph

Step 2: Cypher load commands

MERGE (a:Node {id: 0}) MERGE (b:Node {id: 1}) CREATE (a)-[:RELATION]->(b);
MERGE (a:Node {id: 1}) MERGE (b:Node {id: 2}) CREATE (a)-[:RELATION]->(b);
MERGE (a:Node {id: 3}) MERGE (b:Node {id: 1}) CREATE (a)-[:RELATION]->(b);
MERGE (a:Node {id: 4}) MERGE (b:Node {id: 5}) CREATE (a)-[:RELATION]->(b);
MERGE (a:Node {id: 5}) MERGE (b:Node {id: 6}) CREATE (a)-[:RELATION]->(b);
MERGE (a:Node {id: 7}) MERGE (b:Node {id: 5}) CREATE (a)-[:RELATION]->(b);
MERGE (a:Node {id: 8}) MERGE (b:Node {id: 9}) CREATE (a)-[:RELATION]->(b);
MERGE (a:Node {id: 9}) MERGE (b:Node {id: 10}) CREATE (a)-[:RELATION]->(b);
MERGE (a:Node {id: 11}) MERGE (b:Node {id: 9}) CREATE (a)-[:RELATION]->(b);
MERGE (a:Node {id: 1}) MERGE (b:Node {id: 5}) CREATE (a)-[:RELATION]->(b);
MERGE (a:Node {id: 5}) MERGE (b:Node {id: 9}) CREATE (a)-[:RELATION]->(b);
MERGE (a:Node {id: 2}) MERGE (b:Node {id: 4}) CREATE (a)-[:RELATION]->(b);
MERGE (a:Node {id: 6}) MERGE (b:Node {id: 11}) CREATE (a)-[:RELATION]->(b);
MERGE (a:Node {id: 3}) MERGE (b:Node {id: 8}) CREATE (a)-[:RELATION]->(b);

Step 3: Running command

CALL betweenness_centrality.get(TRUE,TRUE)
YIELD node, betweenness_centrality
RETURN node, betweenness_centrality;

Step 4: Results

+-------------------------+-------------------------+
| node                    | betweenness_centrality |
+-------------------------+-------------------------+
| (:Node {id: 0})         | 0                       |
| (:Node {id: 1})         | 0.109091                |
| (:Node {id: 2})         | 0.0272727               |
| (:Node {id: 3})         | 0                       |
| (:Node {id: 4})         | 0.0454545               |
| (:Node {id: 5})         | 0.2                     |
| (:Node {id: 6})         | 0.0636364               |
| (:Node {id: 7})         | 0                       |
| (:Node {id: 8})         | 0.0181818               |
| (:Node {id: 9})         | 0.0909091               |
| (:Node {id: 10})        | 0                       |
| (:Node {id: 11})        | 0.0181818               |
+-------------------------+-------------------------+