Betweenness Centrality
- Introduced by
- Freeman, L. C.
- Year
- 1977
- Type
- Centrality measure
- Family
- Network science
What does it do?
Betweenness centrality, formalized by Linton C. Freeman in 1977, measures how often a node lies on the shortest path connecting every other pair of nodes in a network.
High-betweenness nodes act as bridges or brokers: removing them fragments the network into disconnected components more severely than removing any other nodes.
The intuition behind the method
Think of a city road network in which all cross-country routes funnel through a single junction. That junction has maximum betweenness even if it has only a moderate number of roads. In a social network, a person who routinely passes information between two otherwise disconnected cliques occupies the same position: they may not know many people directly, but they sit on the critical path that holds the network together. Betweenness centrality quantifies exactly that brokerage role, independent of raw connection count.
History
Linton Freeman formalized betweenness centrality in his landmark 1977 Sociometry paper, drawing on earlier informal uses of the concept by Bavelas (1948) in communication experiments. Freeman's formulation unified several loose intuitions about node importance into a single computable measure and became the canonical definition used in network science. Ulrik Brandes's 2001 algorithm reduced computation from O(V^3) to O(VE), making betweenness centrality practical for networks with thousands of nodes and cementing its place as a standard tool in social network analysis software.
When to use it
Use betweenness centrality when your research question is about brokerage, gatekeeping, or bridge nodes — actors whose removal would disrupt information flow or network cohesion. It is appropriate for undirected and directed graphs, and for weighted graphs where edge weights represent distance or cost. It is especially valuable in communication networks, citation networks, collaboration graphs, and supply chains. Do not use it as the sole centrality measure when brokerage is not the theoretical focus: degree centrality is simpler and sufficient for pure connectivity questions, and eigenvector or PageRank centrality better captures prestige propagation. Avoid it for very large sparse networks without an efficient implementation, as naive computation is O(V^2 E).
Limitations and considerations
- Computationally expensive on very dense networks even with Brandes algorithm; approximation algorithms may be needed for web-scale graphs.
- Assumes actors use shortest paths, which may be unrealistic in networks where flows traverse longer routes (e.g., random walks in electrical networks).
- Sensitive to missing or noisy edges: even a few unobserved ties can dramatically shift betweenness rankings.
- Gives equal weight to all shortest paths even when edge capacities or relationship strengths differ substantially.
Source conditions do not replace independent scientific review or validation by an analysis engine.
Strengths
- Captures structural brokerage and bridge roles that degree and eigenvector centrality miss entirely.
- Applicable to directed, undirected, weighted, and unweighted networks with the same formula.
- Normalized score enables meaningful comparison of nodes within one network and across networks of different sizes.
- Brandes algorithm makes computation tractable for networks with millions of nodes when implemented in optimized libraries such as NetworkX or igraph.
- Well-grounded theoretical interpretation: high-betweenness nodes are empirically associated with information control, power, and structural holes in organizational and social research.
Applications
- Identifying gatekeepers and information brokers in organizational communication networks.
- Detecting critical infrastructure nodes in transportation, power grid, and internet topology studies.
- Finding key intermediary authors or papers in citation and collaboration networks.
- Mapping structural holes and brokerage positions in inter-firm alliance networks.
- Locating influential spreaders in epidemiological and rumor diffusion models.
- Prioritizing nodes for targeted interventions (e.g., vaccination, disruption) in public health and security research.
How it works
How it works
For every ordered pair of distinct nodes (s, t) in the network, all shortest paths (geodesics) between them are identified. For weighted graphs, shortest paths are defined by minimum total edge weight; for unweighted graphs, by fewest hops. This step establishes the universe of paths over which betweenness will be distributed.
For each pair (s, t) the total number of shortest paths sigma(s, t) is counted. When multiple equally short paths exist, each is counted separately. This denominator represents the total shortest-path traffic between s and t without any constraint on routing.
Formula
\sigma(s,t) = \text{number of shortest paths from } s \text{ to } tFor each candidate node v (where v is neither s nor t), the number of those sigma(s, t) shortest paths that actually pass through v is recorded as sigma(s, t | v). The ratio sigma(s, t | v) / sigma(s, t) gives the fraction of shortest-path traffic between s and t that is routed through v.
Formula
\sigma(s,t|v) = \text{shortest paths from } s \text{ to } t \text{ passing through } vThese fractions are summed over all valid pairs (s, t) to produce the raw betweenness score C_B(v). A node whose removal would disconnect many pair-wise shortest paths accumulates a high sum, signalling a structurally critical brokerage position.
Formula
C_B(v) = \sum_{s \neq v \neq t} \frac{\sigma(s,t|v)}{\sigma(s,t)}Raw scores grow with network size, making comparisons across networks of different sizes meaningless. Normalizing by (n-1)(n-2)/2 for undirected graphs (or (n-1)(n-2) for directed) rescales scores to [0, 1], where 1.0 means the node lies on every shortest path and 0 means it lies on none. Brandes (2001) introduced an O(VE) algorithm that computes all betweenness scores simultaneously rather than repeating the search for each node.
Formula
C_B^{\text{norm}}(v) = \frac{C_B(v)}{(n-1)(n-2)/2}Common pitfalls
- Treating high betweenness as equivalent to high degree without checking both; a peripheral node can rank first on betweenness while ranking last on degree.
- Comparing raw (non-normalized) betweenness scores across networks of different sizes.
- Ignoring edge direction in directed networks, which can produce misleading broker identification when flows are asymmetric.
- Applying standard betweenness to weighted networks without confirming that edge weights are correctly interpreted as costs (not similarities) in the shortest-path algorithm.
- Overlooking approximate betweenness methods for large networks and stalling computation on millions of nodes.
Frequently asked questions
How does betweenness centrality differ from degree centrality?
Degree centrality counts direct connections; a hub with many ties scores high. Betweenness centrality counts how often a node lies on shortest paths between others; a bridge connecting two sparse clusters scores high even with few direct ties. The two measures capture orthogonal aspects of structural importance.
Should I use normalized or raw betweenness scores?
Use normalized scores whenever you compare nodes across networks of different sizes or present results to readers unfamiliar with your network's scale. Raw scores are acceptable only for comparisons within a single fixed network where the denominator is constant.
How do I handle weighted edges?
Set edge weights to represent distance or cost, not similarity. Most implementations (NetworkX, igraph) accept a weight parameter interpreted as distance; if your weights represent strength or similarity, invert them (e.g., weight = 1/similarity) before computing betweenness.
Is betweenness centrality meaningful for disconnected networks?
For disconnected graphs, shortest paths between nodes in different components are undefined (infinite). Most software treats those pairs as contributing zero to the sum, which can deflate scores. Either analyze each connected component separately or use a variant such as stress centrality with an explicit treatment of disconnected pairs.
My network has millions of nodes — can I still compute betweenness centrality?
Exact computation with Brandes algorithm is O(VE) and may be too slow. Use randomized approximations (e.g., sampling k source nodes) available in NetworkX (betweenness_centrality with k parameter) or graph libraries like graph-tool, which provide confidence intervals on the approximated scores.
Related methods
Sources
Freeman, L. C. (1977). A set of measures of centrality based on betweenness. Sociometry, 40(1), 35–41.
Open DOI referenceCopied.Brandes, U. (2001). A faster algorithm for betweenness centrality. Journal of Mathematical Sociology, 25(2), 163–177.
Open DOI referenceCopied.