Weighted Betweenness Centrality
- Introduced by
- Opsahl, T.; Agneessens, F.; Skvoretz, J. (extending Freeman 1977 and Brandes 2001)
- Year
- 2010
- Type
- Centrality measure (path-based)
- Family
- Network science
What does it do?
Weighted Betweenness Centrality extends Freeman's betweenness measure to edge-weighted graphs by routing shortest paths through a tunable transformation of edge weights.
Nodes that sit on many high-value shortest paths receive high scores, identifying brokers and bridges in social, biological, and information networks where tie strength matters.
The intuition behind the method
Imagine a city where roads have different traffic capacities. The most influential intersections are not just those with many roads, but those that lie on the fastest or highest-capacity routes between many pairs of locations. Weighted betweenness centrality captures exactly this: it finds nodes that serve as critical relay points, accounting for how strong or weak the connections passing through them are. A node with high weighted betweenness is a bridge or gatekeeper whose removal would disrupt many strong pathways.
History
Betweenness centrality was introduced by Linton Freeman in 1977 as a measure of a node's role in connecting others via shortest paths. Ulrik Brandes developed a landmark efficient algorithm in 2001 that reduced computation from O(n^3) to O(n + m) time for unweighted graphs. The weighted extension was systematically formalised by Opsahl, Agneessens, and Skvoretz in 2010, who proposed the alpha-parameterised weight-to-distance transformation and validated it against empirical collaboration and airline networks.
When to use it
Use weighted betweenness centrality when edge weights represent meaningful tie strength (frequency of contact, flow volume, collaboration intensity, similarity) and you want to identify brokers, gatekeepers, or single points of failure in a network. It is appropriate for social networks, collaboration networks, transportation grids, and biological pathways where the strength of connections shapes which routes are actually used. Avoid it when edge weights are noisy or arbitrary — in that case plain betweenness centrality is safer. Also avoid it for very large networks (millions of nodes) without approximate algorithms, since exact computation is O(n^3) in the worst case.
Limitations and considerations
- Exact computation is O(n^3) in space and time for dense graphs, limiting scalability to very large networks.
- Results are sensitive to the choice of alpha; different values can substantially change the ranking of nodes.
- Assumes that information or influence flows only along geodesic (shortest) paths, which may not reflect real diffusion processes.
- Negative or zero edge weights require special handling and can break shortest-path algorithms.
- Disconnected networks produce undefined betweenness for pairs in different components, requiring component-level analysis.
Source conditions do not replace independent scientific review or validation by an analysis engine.
Strengths
- Captures brokerage and control in networks where tie strength determines which paths are preferred.
- The alpha tuning parameter allows analysts to blend unweighted and fully weighted path logic, making the measure adaptable.
- Directly identifies bottleneck nodes whose removal would fragment or slow the network.
- Compatible with Brandes' efficient algorithm, making computation feasible for networks with tens of thousands of nodes.
- Normalised scores are interpretable across networks of different sizes.
- Well-grounded in a peer-reviewed generalisation framework (Opsahl et al. 2010) with broad citation.
Applications
- Identifying knowledge brokers and boundary spanners in organizational and collaboration networks.
- Locating critical relay nodes in communication or supply-chain networks for resilience analysis.
- Finding hub airports or transit stations that carry the most inter-city traffic in transportation networks.
- Detecting regulatory bottlenecks in protein-interaction or gene-regulatory networks.
- Pinpointing influential spreaders in weighted epidemic or information diffusion models.
- Community-level brokerage analysis in weighted co-authorship and citation networks.
How it works
How it works
Edge weights are converted to distances using an inverse transformation controlled by a tuning parameter alpha. When alpha equals zero the measure reduces to standard unweighted betweenness; as alpha increases toward one, stronger ties are treated as shorter and therefore preferred paths, making the measure sensitive to tie strength.
Formula
d_{ij} = w_{ij}^{-\alpha}, \; \alpha \in [0,1]Dijkstra's algorithm (or Brandes' linear-algebra variant for efficiency) computes the set of shortest weighted paths between every pair of source and target nodes in the network, using the transformed distances. This step identifies which routes are geodesically optimal given the weight configuration.
For every ordered pair of nodes, the algorithm counts the total number of shortest weighted paths and the subset of those paths that pass through each candidate node v. These counts are accumulated efficiently using Brandes' back-propagation technique, keeping the algorithm tractable for moderately large networks.
For each node v, the raw betweenness score is the sum over all source-target pairs of the fraction of their shortest paths that route through v. A node that lies on all shortest paths between a pair contributes 1.0 to its score for that pair; a node bypassed by all paths contributes 0.
Formula
C_B(v) = \sum_{s \neq v \neq t} \frac{\sigma_{st}(v)}{\sigma_{st}}Raw scores are divided by the maximum possible value — which is (n-1)(n-2)/2 for undirected networks — so that scores fall in [0, 1] and are comparable across networks of different sizes. For directed networks the denominator doubles to (n-1)(n-2).
Formula
C_B^{\text{norm}}(v) = \frac{C_B(v)}{(n-1)(n-2)/2}Common pitfalls
- Using the default alpha without reporting or justifying its value — always state and justify your alpha choice.
- Treating raw (unnormalized) scores as comparable across networks of different sizes.
- Ignoring the direction of edges in directed networks and computing undirected betweenness instead.
- Interpreting high betweenness as high influence without considering whether flows actually follow shortest paths in the domain.
- Forgetting to check for disconnected components, which artificially deflate betweenness scores for nodes in smaller components.
Frequently asked questions
How do I choose the alpha parameter?
Alpha controls how much weight influences path choice. At alpha=0 you get classic unweighted betweenness; at alpha=1 stronger ties fully define shortest paths. A common practice is to test alpha=0, 0.5, and 1 and report sensitivity. If the node rankings are stable across values, any choice is defensible; if they differ substantially, justify your choice theoretically based on whether strong ties should be preferred.
What is the difference between weighted and unweighted betweenness centrality?
Unweighted betweenness counts hops; every edge has the same length. Weighted betweenness uses edge weights (converted to distances) so that paths preferentially follow stronger or shorter connections. In networks where tie strength is substantively meaningful — such as frequency of collaboration or volume of trade — the weighted version gives a more accurate picture of which nodes control actual flows.
Is weighted betweenness centrality suitable for very large networks?
Exact computation becomes costly above roughly 100,000 nodes. For very large networks, use approximate algorithms such as random-pivot sampling (implemented in NetworkX as betweenness_centrality with the k parameter) or leverage GPU-accelerated tools like cuGraph. Report whether you used exact or approximate computation.
Can I use weighted betweenness when my network has isolated nodes or multiple components?
Yes, but isolated nodes will always have a score of zero, and nodes in small components will have scores based only on paths within their component. Compute betweenness separately per component if you want within-component rankings, and report the component structure alongside the scores.
How should I report weighted betweenness centrality in a manuscript?
Report the software and version used (e.g., NetworkX, igraph), the value of alpha, whether scores were normalized, how you handled disconnected components, and a summary statistic (mean, range) alongside the top-ranked nodes. A degree-versus-betweenness scatter plot or network visualisation with node size proportional to score aids interpretation.
Related methods
Sources
Opsahl, T., Agneessens, F., & Skvoretz, J. (2010). Node centrality in weighted networks: Generalizing degree and shortest paths. Social Networks, 32(3), 245–251.
Open DOI referenceCopied.Brandes, U. (2001). A faster algorithm for betweenness centrality. Journal of Mathematical Sociology, 25(2), 163–177.
Open DOI referenceCopied.