Betweenness Centrality

Overview

Betweenness centrality measures the likelihood of a node being on the shortest paths between any two other nodes. This metric effectively identifies "bridge" nodes that facilitate connectivity between different parts of a graph.

Betweenness centrality scores range from 0 to 1 (when normalized), with higher scores indicating nodes that exert greater influence over the flow and connectivity of the network.

References:

• L.C. Freeman, A Set of Measures of Centrality Based on Betweenness (1977)
• L.C. Freeman, Centrality in Social Networks Conceptual Clarification (1978)

Concepts

Shortest Path

The shortest paths between two nodes are the paths that contain the fewest edges. When considering edge weights, the (weighted) shortest paths are those with the lowest total weight sum.

Betweenness Centrality

The betweenness centrality of a node x is computed by:

where,

• i and j are two distinct nodes in the graph, excluding x.
• σij is the total number of shortest paths between i and j.
• σij(x) is the number of shortest paths between i and j that pass through node x.
• σij(x)/σij gives the probability that x lies in the shortest paths between i and j. Note that if i and j are not connected, σij(x)/σij is 0.

The final value is normalized by the factor (k – 1)(k – 2), where k is the total number of nodes in the graph. This normalization ensures the result lies within a fixed range, making it comparable across graphs of different sizes.

The betweenness centrality of node A is computed as: (1/2 + 1 + 2/3 + 1/2 + 1 + 2/3) / (4 * 3) = 0.3611111111.

Example Graph

GQL
INSERT (Sue:user {_id: "Sue"}), (Dave:user {_id: "Dave"}),
       (Ann:user {_id: "Ann"}), (Mark:user {_id: "Mark"}),
       (May:user {_id: "May"}), (Jay:user {_id: "Jay"}),
       (Billy:user {_id: "Billy"}),
       (Dave)-[:know {strength: 1}]->(Sue), (Dave)-[:know {strength: 3}]->(Ann),
       (Mark)-[:know {strength: 2}]->(Dave), (May)-[:know {strength: 1}]->(Mark),
       (May)-[:know {strength: 2}]->(Jay), (Jay)-[:know {strength: 2}]->(Ann)

Parameters

Run Mode

Returns:

Normalized betweenness centrality for all nodes:

GQL
CALL algo.betweenness({
  normalized: true,
  order: "desc"
}) YIELD nodeId, score, rank

Result:

Weighted betweenness centrality:

GQL
CALL algo.betweenness({
  ids: ["Dave"],
  normalized: true,
  weight: ["strength"]
}) YIELD nodeId, score, rank

Result:

Stream Mode

Returns the same columns as run mode, streamed for memory efficiency.

GQL
CALL algo.betweenness.stream({
  normalized: true,
  order: "desc"
}) YIELD nodeId, score
FILTER score > 0.1
RETURN nodeId, score

Result:

Stats Mode

Returns:

GQL
CALL algo.betweenness.stats({normalized: true}) YIELD nodeCount, minScore, maxScore, avgScore

Result:

Write Mode

Computes results and writes them back to node properties. The write configuration is passed as a second argument map.

Write parameters:

Writable columns:

Returns:

GQL
CALL algo.betweenness.write({normalized: true}, {
  db: {
    property: "bc_score"
  }
}) YIELD task_id, nodesWritten, computeTimeMs, writeTimeMs