betweennesscentrality

Betweenness centrality is a measure of centrality in a graph that reflects the extent to which a node lies on shortest paths between other nodes. Intuitively, a node with high betweenness acts as a bridge or broker, influencing or controlling communication and flow within the network.

Formal definition: Given a graph G=(V,E), for each pair of distinct nodes s and t with s ≠ t and v ≠ s,t, let σ_st be the number of shortest paths from s to t, and σ_st(v) be the number of those paths that pass through v. The betweenness centrality of v is BC(v) = sum_{s≠v≠t} σ_st(v)/σ_st. In undirected graphs BC(v) is often normalized by dividing by (n-1)(n-2)/2; in directed graphs by (n-1)(n-2).

Computation: The most common exact method is Brandes' algorithm, which aggregates shortest-path information from each source. Its running time is O(nm) for unweighted graphs and O(nm + n^2 log n) for weighted graphs, with memory proportional to the graph size.

Applications and limitations: Betweenness centrality is widely used to identify potential brokers and bottlenecks in social networks, transportation and communication networks, and biological networks. It is sensitive to the overall topology and can be affected by graph size and edge weights; in networks with many equally short paths, exact values can be unstable. It does not measure the quality of those paths or the node's local role beyond path counting, and in directed graphs the direction of flow matters.

Variants exist for weighted graphs, directed graphs, and normalized forms for comparison across networks.