Betweenness Centrality

Overview

Betweenness centrality measures the probability that a node lies in the shortest paths between any other two nodes. Proposed by Linton C. Freeman in 1977, this algorithm effectively detects the 'bridge' or 'medium' nodes between multiple parts of the graph.

Betweenness centrality takes on values between 0 to 1, nodes with larger scores have stronger impact on the flow or connectivity of the network.

Related materials are as below:

• 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

For every pair of nodes in a connected graph, there exists at least one shortest path between the two nodes such that either the number of edges that the path passes through (for unweighted graphs) or the sum of the weights of the edges (for weighted graphs) is minimized.

In the unweighted graph above, we can find three shortest paths between the red and green nodes, and two of them contain the yellow node, so the probability that the yellow node lies in the shortest paths of the red-green node pair is 2 / 3 = 0.6667.

Betweenness Centrality

Betweenness centrality score of a node is defined by this formula:

where x is the target node, i and j are two distinct nodes in the graph (x itself is excluded), σ is the number of shortest paths of pair ij, σ(x) is the number of shortest paths of pair ij that pass through x, σ(x)/σ is the probability that x lies in the shortest paths of pair ij (which is 0 if i and j are not connected), k is the number of nodes in the graph, (k-1)(k-2)/2 is the number of ij node pairs.

Calculate betweenness centrality of the red node in this graph. There are 5 nodes in total, thus (5-1)*(5-2)/2 = 6 node pairs except the red node, the probabilities that the red node lies in the shortest paths between all node pairs are 0, 1/2, 2/2, 0, 2/3 and 0 respectively, so its betweenness centrality score is (0 + 1/2 + 2/2 + 0 + 2/3 + 0) / 6 = 0.3611.

NOTE

Betweenness Centrality algorithm consumes considerable computing resources. For a graph with V nodes, it is recommended to perform (uniform) sampling when V > 10,000, and the suggested number of samples is the base-10 logarithm of the number of nodes (log(V)).

For each execution of the algorithm, sampling is performed only once, centrality scores of all nodes are computed based on the shortest paths between all sample nodes.

Considerations

• The betweenness centrality score of isolated nodes is 0.
• The Betweenness Centrality algorithm ignores the direction of edges but calculates them as undirected edges. In undirected graph of k nodes, there are (k-1)(k-2)/2 node pairs for each target node.

Syntax

• Command: algo(betweenness_centrality)
• Parameters:

Examples

The example graph is a small social network, nodes represent users, and edges represent the relationship of know:

File Writeback

UQL
algo(betweenness_centrality).params().write({
  file:{ 
    filename: 'centrality'
  }
})

Results: File centrality

File
Billy,0
Jay,0.0666667
May,0.0666667
Mark,0.133333
Ann,0.133333
Dave,0.333333
Sue,0

Property Writeback

UQL
algo(betweenness_centrality).params().write({
  db:{ 
    property: 'bc'
  }
})

Results: Centrality score for each node is written to a new property named bc

Direct Return

UQL
algo(betweenness_centrality).params({
  order: 'desc',
  limit: 3
}) as bc
return bc

Results: bc

Stream Return

UQL
algo(betweenness_centrality).params().stream() as bc
where bc.centrality == 0
return count(bc)

Results: 2