betweenness

Betweenness, in the context of network analysis, refers to a measure of centrality that identifies nodes (and, in some variants, edges) that lie on many shortest paths between pairs of other nodes. A node with high betweenness can be important for the control or facilitation of information flow within a network.

Mathematically, the betweenness centrality of a node v is defined as the sum over all pairs of distinct nodes s and t (with s and t not equal to v) of the fraction of shortest paths from s to t that pass through v. If sigma_st is the number of shortest paths from s to t and sigma_st(v) is the number of those paths that pass through v, then centrality(v) = sum_s≠v≠t (sigma_st(v) / sigma_st). In undirected graphs, pairs are often considered once per unordered pair; in directed graphs, ordered pairs are used. There are also normalized versions that scale the value to the interval [0,1].

Variants include edge betweenness, which measures how often an edge lies on shortest paths between node pairs, and weighted betweenness, which accounts for path lengths in graphs with weighted edges. Normalization factors differ by graph type to facilitate comparison across graphs of different sizes.

Computation is typically performed with the Brandes algorithm, which computes betweenness centrality efficiently. For unweighted graphs, it runs in O(nm) time; for weighted graphs, it runs in about O(nm + n^2 log n). Approximation methods exist for very large networks.

Applications span social networks, transportation, biology, and information systems. Betweenness helps identify bottlenecks, potential vulnerabilities, community bridges, and influential conduits for information or disease spread. The concept was popularized in the social network literature by Freeman in the late 1970s.