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 values range from 0 to 1, 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)/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 / 2) = 0.722222.

Sampling

This algorithm requires substantial computational resources when applied to large graphs. When the number of nodes in a graph exceeds 10,000, it is recommended to sample nodes or edges for approximate computation. The algorithm performs a single uniform sampling.

Example Graph

Run the following statements on an empty graph to define its structure and insert data:

GQLUQL
ALTER GRAPH CURRENT_GRAPH ADD NODE {
  user ()
};
ALTER GRAPH CURRENT_GRAPH ADD EDGE {
  know ()-[{strength int32}]->()
};
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);

Creating HDC Graph

To load the entire graph to the HDC server hdc-server-1 as my_hdc_graph:

GQLUQL
CREATE HDC GRAPH my_hdc_graph ON "hdc-server-1" OPTIONS {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static"
}

Parameters

Algorithm name: betweenness_centrality

File Writeback

GQLUQL
CALL algo.betweenness_centrality.write("my_hdc_graph", {
  return_id_uuid: "id"
}, {
  file: {
    filename: "betweenness_centrality"
  }
})

Result:

File: betweenness_centrality
_id,betweenness_centrality
Dave,0.666667
Billy,0
May,0.133333
Mark,0.266667
Jay,0.133333
Ann,0.266667
Sue,0

DB Writeback

Writes the betweenness_centrality values from the results to the specified node property. The property type is float.

GQLUQL
CALL algo.betweenness_centrality.write("my_hdc_graph", {}, 
{
  db: {
    property: "bc"
  }
})

Full Return

GQLUQL
CALL algo.betweenness_centrality.run("my_hdc_graph", {
  max_path_length: 2,
  return_id_uuid: "id",
  order: "desc",
  limit: 3
}) YIELD bc
RETURN bc

Result:

Stream Return

GQLUQL
CALL algo.betweenness_centrality.stream("my_hdc_graph", {
  return_id_uuid: "id",
  edge_schema_property: "strength"
}) YIELD r
FILTER r.betweenness_centrality > 0.6
RETURN r

Result: