Wait, What?
A node can be important even when it has very few neighbours.
Betweenness centrality measures how often a vertex sits on shortest paths between other vertices. That sounds simple until you try to compute it directly: there can be many source–target pairs, and many pairs can have several equally short paths. Brandes’ algorithm is the classic breakthrough that reorganises the calculation so one shortest-path search from each source can contribute to the betweenness score of every reachable vertex.
The deeper lesson is bigger than one graph metric. Brandes shows how to reuse information from a shortest-path computation, build a dependency structure, and accumulate answers backwards instead of recomputing the same paths again and again.
Quick Answer
Learn Brandes’ algorithm in this order: shortest paths → multiple shortest paths → betweenness definition → predecessor DAG → path counts σ → reverse dependency accumulation δ → unweighted implementation → weighted implementation → normalisation → approximation and scale. For beginners, the key idea is “count shortest routes without listing every route.” For professionals, the key idea is “reuse one single-source shortest-path computation to aggregate all pair dependencies efficiently.”
1. First understand what betweenness centrality is measuring
Suppose a school has several classroom blocks connected by walkways. One narrow corridor may connect two large parts of the campus. It might have only two immediate neighbours, yet many shortest routes between rooms pass through it. Degree centrality would not necessarily call that corridor important. Betweenness centrality can.
For a vertex v, shortest-path betweenness is based on the fraction of shortest paths from s to t that pass through v:
C_B(v) = Σ_{s ≠ v ≠ t} σ_st(v) / σ_stHere, σ_st is the number of shortest paths from s to t, and σ_st(v) is the number of those shortest paths that pass through v.
The word fraction matters. If there are four equally short routes between s and t and only one uses v, then that pair contributes one quarter, not one whole unit.
2. Why the obvious algorithm is wasteful
A naive strategy might do this for every pair (s,t): find all shortest paths, count them, check which vertices occur on them, then update scores. That repeats massive amounts of work. The shortest paths from one fixed source s overlap heavily. If several targets share early path segments, recomputing those segments separately is unnecessary.
Brandes’ insight is to group work by source. From one source s, run a single-source shortest-path algorithm once, record enough structure, then use a backward pass to distribute dependency contributions to predecessors.
3. The three data structures you must understand
For each source s, Brandes’ algorithm maintains three conceptual records.
- Distance d[v]: shortest distance from s to v.
- Path count σ[v]: number of shortest paths from s to v.
- Predecessors P[v]: vertices that can immediately precede v on a shortest path from s.
These predecessor links form a shortest-path directed acyclic structure ordered by nondecreasing distance from s. You do not need to enumerate every complete shortest path. You only need enough local structure to reconstruct how shortest-path flow can arrive at each vertex.
4. Trace the forward pass on a tiny graph
Take an unweighted graph with edges:
A—B, A—C, B—D, C—D, D—ELet A be the source. The shortest distances are d[A]=0, d[B]=d[C]=1, d[D]=2, d[E]=3.
There is one shortest path from A to B and one from A to C. Vertex D has two shortest paths from A: A–B–D and A–C–D. Therefore σ[D]=2. Vertex E inherits both shortest routes through D, so σ[E]=2.
The predecessor sets are P[B]={A}, P[C]={A}, P[D]={B,C}, and P[E]={D}. This small example is enough to see why simply storing one parent would be wrong. Multiple equal-length parents are essential to the metric.
5. The reverse pass: dependency accumulation
Once the shortest-path structure is known, process vertices in reverse order of distance from the source. Define δ[v] as the dependency of source s on vertex v: roughly, how much of the source’s shortest-path responsibility flows back through v.
For a predecessor v of a vertex w, the standard contribution is:
δ[v] += (σ[v] / σ[w]) × (1 + δ[w])The ratio σ[v]/σ[w] splits responsibility among predecessor routes. The term 1+δ[w] includes both the direct contribution of reaching w and the dependencies that w has already accumulated from vertices farther away.
After processing w, add δ[w] to w’s betweenness score unless w is the source.
6. Why the reverse order is not optional
The dependency of a vertex depends on contributions from vertices farther from the source. Therefore those farther vertices must be resolved first. In an unweighted graph, a BFS naturally discovers vertices in nondecreasing distance order. Brandes stores that order in a stack and pops it backwards.
This is a recurring algorithmic pattern: do a forward pass to build dependencies, then a reverse pass to aggregate them. Dynamic programming on DAGs, automatic differentiation and many tree algorithms use a similar shape.
7. Conceptual pseudocode for an unweighted graph
for each vertex v:
centrality[v] = 0
for each source s:
stack = []
predecessors[v] = [] for all v
sigma[v] = 0 for all v
sigma[s] = 1
distance[v] = -1 for all v
distance[s] = 0
queue = [s]
while queue not empty:
v = pop_front(queue)
push(stack, v)
for each neighbor w of v:
if distance[w] < 0:
distance[w] = distance[v] + 1
push_back(queue, w)
if distance[w] == distance[v] + 1:
sigma[w] += sigma[v]
predecessors[w].append(v)
delta[v] = 0 for all v
while stack not empty:
w = pop(stack)
for v in predecessors[w]:
delta[v] += (sigma[v] / sigma[w]) * (1 + delta[w])
if w != s:
centrality[w] += delta[w]This is not production code. Its purpose is to make the invariant visible.
8. Weighted graphs change the shortest-path engine
For unweighted graphs, Brandes uses BFS. For positively weighted graphs, the forward pass becomes a Dijkstra-style shortest-path computation. The dependency accumulation idea remains the same, but path-count updates must respect equal-distance alternatives correctly.
Current NetworkX documentation also warns that weighted betweenness expects positive edge weights. Zero-weight edges can create an unbounded number of equal-length walks under some interpretations, which makes path counting ambiguous.
9. Complexity: where the speedup comes from
Brandes’ 2001 result reduced the classic full computation to O(VE) time on unweighted graphs and O(VE + V² log V) for weighted graphs with a suitable priority queue, while using O(V+E) working memory for the core computation.
That is still expensive on very large graphs because the algorithm runs a shortest-path search from every source. But it is dramatically better than approaches that effectively enumerate pairwise path structure redundantly.
10. Normalisation is part of the definition
Raw betweenness scores depend strongly on graph size. Libraries often provide normalised forms so scores can be compared more meaningfully. Directed and undirected graphs require different counting conventions because an undirected pair s–t is not normally counted twice as two independent directions.
Before comparing results from two libraries, verify:
- whether endpoints are included;
- whether the graph is directed;
- whether weights are interpreted as distances;
- whether results are normalised;
- how disconnected pairs are treated.
11. Approximation: when exact betweenness is too expensive
Modern graph libraries can estimate betweenness by sampling a subset of source vertices. In NetworkX, the k parameter selects sampled pivots. Fewer pivots reduce work but increase estimation error.
Professional practice should therefore report the sampling method, random seed, number of pivots, graph size, and whether the result is exact or approximate. A centrality score without its computational contract is easy to overinterpret.
12. Betweenness is not importance in every sense
A high betweenness vertex is important under a shortest-path traffic model. Real systems may route differently. Information may diffuse, travellers may choose near-shortest routes, failures may reroute traffic, or direction and capacity may matter.
Do not turn the metric into a universal claim such as “this person is the most influential.” The algorithm computes a precise quantity. The modelling assumption that makes that quantity meaningful must be defended separately.
13. Edge betweenness and community structure
The same dependency machinery can compute edge betweenness. Edges that carry a large share of shortest-path traffic can act like bridges between regions of a network. Some community-detection methods repeatedly remove high-betweenness edges, although that creates a separate algorithmic job and should not be confused with Brandes’ core centrality computation.
14. How to teach Brandes from beginner to professional
Programming-education research strongly supports code comprehension before unsupported code writing. A useful progression is:
- Predict: on a five-node graph, predict which node has highest betweenness and why.
- Run: compare the prediction with a library result.
- Investigate: trace BFS distances, σ counts, predecessor sets and δ values.
- Modify: add an edge that creates a second shortest path and predict the score changes.
- Make: implement Brandes from scratch and validate against a trusted library.
For novices, Parsons-style exercises can reduce syntax load: give shuffled blocks for the BFS phase or reverse dependency phase and ask learners to reconstruct the correct order before writing full code.
15. Debugging checklist
- Did you initialise σ=1?
- Do you append all predecessors that preserve shortest distance?
- Do you accumulate σ for equal-length alternatives?
- Is the reverse pass truly in nonincreasing distance order?
- Are you excluding the source from its own betweenness accumulation?
- Are directed and undirected normalisation rules consistent?
- For weighted graphs, are weights positive and treated as distances?
16. Professional validation strategy
Build tests in layers. Start with paths, stars, cycles and cliques where qualitative results are obvious. Then generate small random graphs and compare your implementation with NetworkX. Next test disconnected graphs, directed graphs, graphs with multiple equal shortest paths, and weighted graphs. Finally profile time and memory separately.
For approximation, add stability tests across seeds and pivot counts. A professional implementation should expose uncertainty created by sampling rather than hide it.
17. Common failure states
- Counting only one shortest path when several exist.
- Using a DFS tree instead of the shortest-path predecessor DAG.
- Running the reverse pass before all downstream dependencies are known.
- Using edge “strength” directly as a distance without transforming its meaning.
- Comparing raw scores across graphs of very different sizes.
- Calling high betweenness “influence” without defending the shortest-path model.
- Sampling sources but presenting the output as exact.
18. Practice ladder
- Beginner: calculate betweenness manually on a five-node path and a star.
- Foundation: trace σ and predecessor sets from one source.
- Intermediate: implement the unweighted Brandes algorithm.
- Advanced: extend it to positive weighted graphs and verify equal-distance handling.
- Professional: compare exact and sampled betweenness on graphs of increasing size, documenting error, runtime, memory and modelling assumptions.
19. Ownership boundary
This article owns the algorithmic job of efficiently computing shortest-path betweenness centrality using Brandes’ forward shortest-path phase and reverse dependency accumulation. It does not replace general shortest-path teaching, PageRank, community detection, current-flow centrality or graph visualisation.
Sources and further reading
- Ulrik Brandes, “A Faster Algorithm for Betweenness Centrality,” The Journal of Mathematical Sociology, 25(2), 2001. DOI: 10.1080/0022250X.2001.9990249.
- NetworkX 3.6.1 documentation, betweenness_centrality, including exact, weighted and sampled variants.
- Sue Sentance and collaborators on PRIMM; current educator guidance is available through the Raspberry Pi Foundation Training Hub.
- Recent computing-education research on Parsons and faded Parsons problems supports structured code-ordering tasks as a bridge from comprehension to independent coding.
Professional rule: you understand Brandes’ algorithm when you can explain why one shortest-path search from a source is enough to distribute that source’s contribution to every vertex without enumerating every shortest path explicitly.
