Betweenness Centrality

Definition

Bridge node with degree 2 but betweenness 9 showing how all left-to-right shortest paths must pass through it

Betweenness centrality measures how often a node lies on the shortest paths between other pairs of nodes — its role as a bottleneck or connector.

$C_B(v) = \sum_{s \neq v \neq t} \frac{\sigma_{st}(v)}{\sigma_{st}}$

where:

$\sigma_{st}$ = total number of shortest paths from node $s$ to node $t$ .
$\sigma_{st}(v)$ = number of those shortest paths that pass through node $v$ .
The sum is over all ordered pairs $(s, t)$ with $s \neq v$ , $t \neq v$ , and $s \neq t$ .

Interpretation: a node with high betweenness centrality is critical for communication or flow through the network. If you remove it, many pairs of nodes must use longer alternative paths (or become disconnected). It is the network-analogue of a bridge in a road system: without it, journeys become much longer.

CRITICAL: Halving for Undirected Graphs

For undirected graphs, every shortest path from $s$ to $t$ is identical to the path from $t$ to $s$ . Both $(s, t)$ and $(t, s)$ appear in the summation. Therefore, every path is double-counted. After computing $C_B(v)$ from all ordered pairs, halve the score.

Common exam error: forgetting to halve. An answer of 6 instead of 3 loses the mark.

Betweenness centrality is the measure to use for finding connectors: people who, without necessarily being central to any particular social circle, serve as bridges between them. A connector lies on many shortest paths between members of different groups.

This is distinct from degree: a node can have high degree (many friends within one community) but low betweenness (it doesn’t bridge to other communities). Conversely, a node can have moderate degree but high betweenness if it’s the sole link between two otherwise separate groups.

Edge betweenness is the analogous measure for edges: how many shortest paths pass through this edge? It is the key quantity in the Newman-Girvan community detection algorithm.

Qualitative Worked Example: 2025 Q8 Graph

Graph: A–B, A–E, B–C, B–F, C–D, C–F, D–F, D–H, F–G, G–H.

Node A (Moderate-High Betweenness)

A connects to leaf E and to B (which connects to the rest of the graph). All paths from E to any other node MUST pass through A, because E has exactly one neighbour. For 6 other nodes (B, C, D, F, G, H), that is 6 paths through A out of 6 total paths starting from E.

Before halving: paths from E → each of 6 nodes = 6. After halving: $C_B(A) \approx 3$ .

Node C (Moderate-High Betweenness)

C lies on many shortest paths between the {A, B, E} “left cluster” and the {D, H, G, F} “right cluster.” Routes from A, B, E to D, H, G often pass through C or F. C has moderate-to-high betweenness because it serves as one of two main connectors between the two halves of the graph (the other being F).

Node H (Low Betweenness)

H is at the end of two edges: D–H and G–H. For most source–target pairs, H is not on the shortest path between them — because H is at a “dead end” of the graph. If H is the source or target, it is excluded from the sum ( $s \neq v \neq t$ ). So H contributes only when some shortest path between two other nodes happens to pass through H. In this graph, very few do. $C_B(H)$ is low.

Effect of Edge Changes (2025 Q8e)

Remove D–H and add C–E:

Remove D–H: H now connects only via G → F → cluster. All paths to/from H now go through G. $C_B(G)$ increases substantially. $C_B(H)$ decreases: H becomes a leaf, and no shortest paths pass THROUGH a leaf (only TO or FROM it).
Add C–E: E now has two neighbours (A and C), so it is no longer a leaf. Some paths from E to the right-side cluster (D, H, G, F) can now go via C directly instead of through A. $C_B(A)$ decreases (loses some E-paths). $C_B(C)$ increases (gains E-paths). E gains moderate betweenness as it lies on its own new paths.

Summary

Concept	Key Point
Formula	$C_B(v) = \sum_{s \neq v \neq t} \frac{\sigma_{st}(v)}{\sigma_{st}}$
Undirected correction	Halve all scores at the end
High betweenness	Connector/bottleneck between communities
Low betweenness	Leaf node, peripheral node with few bridging paths
Use case	Finding connectors in social networks; Newman-Girvan edge removal

Past paper questions: y2020p3q9, y2025p3q8