betweennesscentralitet

Betweennesscentralitet is a centrality measure used in network analysis to quantify how often a node lies on the shortest paths between pairs of other nodes. It captures a node’s potential to act as a bridge or broker within a network. The concept is commonly referred to in English as betweenness centrality.

Mathematically, for a graph G = (V, E), the betweenness centrality of a node v is defined as BC(v) = sum over all pairs s, t in V with s ≠ t and s ≠ v ≠ t of σ_st(v) / σ_st, where σ_st is the number of shortest paths from s to t and σ_st(v) is the number of those paths that pass through v. In undirected graphs, the value is often normalized by dividing by the total number of pairs, yielding a range from 0 to 1. For directed graphs, the normalization factor differs accordingly.

Computationally, the standard approach is based on Brandes’ algorithm, which computes the centrality for all nodes efficiently. For unweighted graphs, the running time is O(nm), where n is the number of nodes and m the number of edges. For weighted graphs, a variant using Dijkstra’s algorithm from each source node is typically used, with a complexity about O(n(m + n log n)). In very large networks, approximate methods or sampling can provide near-accurate estimates with reduced cost.

Interpretation and limitations: Nodes with high betweenness centrality lie on many shortest paths and can control information flow, act as bottlenecks, or connect communities. However, the measure depends on the current network structure and on the presence of multiple shortest paths, which can introduce sensitivity to small changes. It does not directly reflect node importance due to degree or other factors.

Applications include social networks, transportation and communication networks, biological networks, and infrastructure analysis, where identifying brokers, bridges, or vulnerable points is valuable.