Brandes' Algorithm for Betweenness Centrality

Motivation

Computing betweenness centrality naïvely requires finding all-pairs shortest paths, which takes $O(|V|^3)$ with Floyd-Warshall or $O(|V|^2 \log |V| + |V| \cdot |E|)$ with repeated Dijkstra. Brandes’ algorithm (2001) reduces this to $O(|V| \cdot |E|)$ for unweighted graphs by reusing intermediate computations across source vertices.

Key Insight

For each source vertex $s$, run a single BFS (or Dijkstra for weighted graphs) to compute the shortest-path directed acyclic graph (DAG) rooted at $s$. Then accumulate dependency values backwards — from the farthest nodes to the root — in a single reverse traversal. This avoids recomputing path counts for every target independently.

Algorithm Steps

Forward Pass — BFS from Each Source $s$

Run BFS from $s$ to discover nodes in order of increasing distance. For each node $v$:

• $\sigma_s[v]$: the number of distinct shortest paths from $s$ to $v$.
  • For the source: $\sigma_s[s] = 1$.
  • For a neighbour $v$ of $u$: if $v$ is newly discovered (first time reaching it at this depth), set $\sigma_s[v] = \sigma_s[u]$ and record $u$ as a predecessor of $v$.
  • If $v$ is rediscovered at the same depth (another shortest path to $v$ of the same length), add $\sigma_s[u]$ to $\sigma_s[v]$ and add $u$ to $P_s(v)$ (the predecessor set).
• $P_s(v)$: the set of nodes $u$ such that the edge $u \to v$ lies on at least one shortest path from $s$ to $v$.

The result is a shortest-path DAG: edges only go from nodes at distance $d$ to nodes at distance $d+1$.

Backward Pass — Accumulate Dependencies

Process nodes in reverse BFS order (farthest from $s$ first, closest last). For each node $v$ (excluding $s$):

$\delta_s(v) = \sum_{w \;:\; v \in P_s(w)} \frac{\sigma_s[v]}{\sigma_s[w]} \cdot \big(1 + \delta_s(w)\big)$

This says: $v$‘s dependency contribution to paths ending at $w$ is proportional to the fraction of shortest paths from $s$ to $w$ that pass through $v$, plus the dependency that $w$ itself accumulates from nodes beyond it.

Add $\delta_s(v)$ to $C_B(v)$.

Undirected Correction

For undirected graphs, each unordered pair $(s, t)$ appears twice in the summation (once as $(s, t)$ and once as $(t, s)$). After summing over all sources $s$, halve all betweenness scores.

Complexity

Graph Type	Algorithm Used	Time Complexity
Unweighted	BFS from each source	$O(\lvert V \rvert \cdot \lvert E \rvert)$
Weighted	Dijkstra from each source	$O(\lvert V \rvert \cdot \lvert E \rvert + \lvert V \rvert^2 \log \lvert V \rvert)$

This is close to optimal for dense graphs: all-pairs shortest paths inherently requires examining all edges from all sources, which is $\Omega(|V| \cdot |E|)$ in the worst case.

What the Exam Expects

The full dependency-accumulation formula is beyond the scope of most MLRD exam questions. What you should know:

1. Brandes runs BFS (or Dijkstra) from every source node, giving $O(|V| \cdot |E|)$ total time.
2. The forward pass computes shortest-path DAGs and $\sigma$ counts (number of shortest paths to each node).
3. The backward pass accumulates dependencies from farthest nodes backward to the root.
4. For undirected graphs, halve the final betweenness scores.
5. This algorithm is used in practice to compute edge betweenness for Newman-Girvan community detection: edge betweenness is computed by summing the dependency contributions that flow through each edge during the backward pass.

Connection to Newman-Girvan

Newman-Girvan repeatedly removes edges with highest betweenness. Computing edge betweenness for all edges naïvely after each removal would be extremely expensive. Brandes makes this feasible: after each edge removal, recompute all-pairs shortest paths in $O(|V| \cdot |E|)$. The algorithm is run repeatedly until the desired number of clusters is reached.

Summary

Step	Operation
Overall approach	BFS/Dijkstra from every source, accumulate dependencies backward
Forward pass	Compute $\sigma_s[v]$ (path counts) and predecessors $P_s(v)$
Backward pass	Accumulate $\delta_s(v)$ from farthest nodes to source
Complexity (unweighted)	$O(\lvert V \rvert \cdot \lvert E \rvert)$
Complexity (weighted)	$O(\lvert V \rvert \cdot \lvert E \rvert + \lvert V \rvert^2 \log \lvert V \rvert)$
Undirected correction	Halve all final betweenness scores

Past paper questions: y2025p3q8 (Newman-Girvan context)