Not who has the most friends — who sits between everyone else. Betweenness scores each vertex by the fraction of all shortest paths that pass through it: the broker, the choke point, the node whose removal splits the network. Down the center, data flows: the graph goes in, the engine sums the paths, the scores come out. The blue team builds and defends it against brute force; the red team tries to break it.
source Freeman, L.C., A Set of Measures of Centrality Based on Betweenness (1977), Sociometry 40(1), 35–41, DOI 10.2307/3033543 — jstor.org/stable/3033543. Rendered, not quoted.
For a vertex v, betweenness is a sum over every pair of other vertices s, t:
CB(v) = Σs≠v≠t σst(v) / σst
σst = how many shortest paths run from s to t; σst(v) = how many of them pass through v. A node on every route scores high; a dead-end leaf scores 0. Live scores on the network at center:
| node | raw | normalized |
|---|
Freeman (1977) made an old intuition of Bavelas computable: importance is control of communication — how much of the network's shortest-path traffic must route through you.
Every score here is built from shortest paths, so this sphere stands on the-dijkstra: Dijkstra finds one shortest path; betweenness aggregates all of them and asks whose removal fractures the graph. Each sphere is the next one's premise.
The blue team's live check: recompute betweenness by the fast engine and confirm it against brute force over all simple paths, plus the global identity ΣCB ≡ Σ(d−1) on a fixed-seed ensemble. If red tampers, this badge is where it shows.
A small communication network: two tight groups joined only through Cal, with Fay hanging off Ana as a pendant. Six people, seven ties, all undirected:
Ana–Ben, Ben–Cal, Cal–Ana (left triangle) · Cal–Dee, Dee–Eve, Eve–Cal (right triangle) · Ana–Fay (leaf).
A=Ana · B=Ben · C=Cal (the only bridge) · D=Dee · E=Eve · F=Fay (leaf). Feed this into the engine below.
Raw betweenness: the count of shortest-path pairs each node sits in the middle of.
Every bar is computed on the spot — Brandes accumulation over BFS shortest-path counts — never looked up.
What the machine proves: Cal = 6 is the highest betweenness — every message between the two groups routes through Cal, and removing Cal splits the network in two. Ana = 4 brokers Fay to everyone. The leaf Fay = 0: a dead end is never in anyone's way. Each score is exact against brute force over all paths.
The blue team's witness (left) confirms these numbers live; the red team (right) tries to make them wrong.
It is also expensive — O(nm) unweighted (Brandes 2001), and brute enumeration of all paths is exponential, so this instrument only stays honest on a small graph. Add one edge and the ranking can jump: betweenness is not stable to the network you failed to measure.
"The most-connected node is the most central." Cut. Degree and betweenness disagree here: Cal and Ana both have degree 3, but Cal scores 6 and Ana 4 — position, not popularity.
"A leaf still carries some traffic." Cut. A degree-1 node is never interior to any shortest path. Fay's betweenness is exactly 0, proven by the engine.
"Betweenness needs weighted edges." Kept, corrected. It is defined on shortest paths of any metric; on an unweighted graph the metric is hop-count — still exact.
The red team's move: make the engine count only shortest paths of length ≤ 2 and ignore the longer ones. The bridge's cross-group traffic gets under-counted. The blue team's witness (window 7) is watching.
Cap the path length and Cal's score drops from 6 to 4 — the two distance-3 routes to Fay vanish. The witness recomputes, disagrees with brute force, and turns red. Nothing is faked; the attack is real and it is caught.