betweennesssentralitet

Betweennesscentralitet, or betweenness centrality, is a measure in network analysis that quantifies how often a node lies on the shortest paths between pairs of other nodes. It reflects a node’s role as a bridge or broker in facilitating communication or flow through the network.

For a given graph, let σ_st be the number of shortest paths from node s to node t, and let σ_st(v) be the number of those paths that pass through node v. The betweenness centrality of v is defined as C_B(v) = sum over all s ≠ v ≠ t of σ_st(v) / σ_st. This can be computed for directed or undirected graphs, and for weighted graphs the concept uses the shortest-path distances with the respective weights. Normalization is often applied to compare networks of different sizes: in undirected graphs with n nodes, the maximum possible C_B(v) is (n−1)(n−2)/2; in directed graphs it is (n−1)(n−2). The normalized centrality is C_B(v) / max.

Computation is commonly performed with Brandes’ algorithm, which computes betweenness in O(nm) time for unweighted graphs and O(nm + n^2 log n) for weighted graphs, where n is the number of nodes and m the number of edges. For very large networks, approximate or sampling-based methods may be used.

Interpretation and limitations: a high betweenness score indicates that a node often serves as a bridge, potentially exerting control over information or traffic flow. It does not necessarily correspond to degree or influence and can be sensitive to network completeness and edge directionality. Betweenness centrality is widely used in social network analysis, transportation, biology, infrastructure, and information networks to identify bottlenecks, gateways, and articulation-like roles.