Module betweenness 

Betweenness centrality (Brandes 2001).

The betweenness centrality of a node v measures how often v lies on a shortest path between two other nodes:

C_B(v) = Σ_{s ≠ v ≠ t}  σ_{st}(v) / σ_{st}

where σ_{st} is the number of shortest s → t paths and σ_{st}(v) is the number of those that pass through v.

Brandes’ algorithm computes all pairwise contributions in O(n·m) time (for unweighted graphs) without ever materialising the O(n²) pair table. For each source s it

1. runs a BFS that records, for every node, its shortest-path distance, the number of shortest paths σ from s, and the set of predecessors on those paths, and
2. accumulates dependencies δ_s(v) by walking the BFS-discovered nodes in order of non-increasing distance, using the recurrence

   δ_s(v) = Σ_{w : v ∈ pred(w)} (σ_v / σ_w) · (1 + δ_s(w)).

The adjacency list is interpreted as a directed graph. For an undirected graph supply a symmetric adjacency list; the returned scores then follow the usual convention of including each unordered pair twice (the values are not halved here, matching the directed accumulation).

Reference: U. Brandes, “A faster algorithm for betweenness centrality”, Journal of Mathematical Sociology, 2001.

Functions

betweenness_centrality

Compute the (shortest-path) betweenness centrality of every node.