Betweenness Centrality

Picture a social network. One person has hundreds of friends — clearly important. But there is someone else, with only a handful of connections, who happens to be the single link between two otherwise separate crowds. Remove the popular person and the network barely notices. Remove the quiet connector and the network splits in two.

That quiet connector is what betweenness centrality measures. Instead of counting how many friends you have, it counts how often you lie on the shortest path between two other people. The more pairs that must route through you to reach each other, the higher your betweenness — and the more of a broker you are.

It is a beautifully simple idea with a surprising payoff: it finds the bridges, gatekeepers and bottlenecks that raw popularity completely misses.

Below is a small friendship network. Press Compute betweenness and each node fills with color in proportion to how often it sits on the shortest paths between every other pair. The brightest nodes are the brokers.

<p class="hint">{{hint}}</p>
<svg id="net" viewBox="0 0 420 260" role="img" aria-label="{{net_aria}}"></svg>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="compute" type="button">{{btn_compute}}</button>
  <button id="bridge" type="button">{{btn_bridge}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
#net { width: 100%; height: auto; background: #f4f7fa; border: 1px solid #dde5ec; border-radius: 10px; }
.edge { stroke: #9fb2c8; stroke-width: 2.5; }
.edge.cut { stroke: #e63946; stroke-width: 2.5; stroke-dasharray: 5 4; }
.node circle { stroke: #1d3557; stroke-width: 2; fill: #ffffff; transition: fill .35s; }
.node text { font: 700 12px system-ui, sans-serif; fill: #1d3557; text-anchor: middle; dominant-baseline: middle; }
.node .score { font: 600 10px ui-monospace, monospace; fill: #355; }
.status { font-size: 1rem; font-weight: 600; margin: .55rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Watch what happens when you cut the bridge: the single edge joining the two clusters carries almost every cross-cluster path, so its endpoints glow. Remove it and the network fragments — exactly the kind of weak point betweenness is built to expose. Notice that the most connected node is not always the most between.

How hard is it to compute betweenness for every node? This is a solved problem — and pleasantly so.

• The naive way is to find all shortest paths between every pair of nodes and tally who lies on them. Done carelessly, accumulating contributions pair-by-pair costs roughly $O(V^{3})$ time and even $O(V^{2})$ memory to store the paths.
• Brandes' algorithm (Ulrik Brandes, 2001) is the breakthrough. It runs one shortest-path search (a BFS for unweighted graphs) from each node, then sweeps backward through the search, accumulating each node's contribution in a single pass — no need to enumerate paths explicitly.
• The result: exact betweenness for all nodes in $O(V \cdot E)$ time on unweighted graphs (and $O(V \cdot E + V^{2} \cdot \log V)$ with weights), using only $O(V + E)$ memory.

That efficiency is what turned betweenness from a textbook curiosity into a tool you can run on real million-node networks. Unlike the hardest problems behind P vs NP, there is no exponential wall here — just clever bookkeeping. For very large graphs, sampling a subset of source nodes gives accurate estimates even faster.

"Which point, if removed, would do the most damage?" is a question with a startling number of real owners:

• Social network analysis: brokers control the flow of information and influence; targeting them is the fastest way to fragment or to seed a network.
• Epidemiology: high-betweenness people are bridges between communities — vaccinate or isolate them and you cut the most transmission paths.
• Infrastructure and traffic: roads, routers and power lines with high betweenness are bottlenecks whose failure cascades the furthest.
• Community detection: the famous Girvan–Newman method repeatedly removes the highest-betweenness edges, peeling a network apart into its natural communities.

Betweenness sits alongside other graph measures like PageRank, and the bridges it exposes are exactly the cuts studied in problems like maximum flow.

Betweenness centrality captures something popularity never can: not how many friends you have, but how indispensable you are to everyone else's connections. The quiet broker on the only bridge between two crowds scores higher than the loudest hub — and removing them does the most damage.

Best of all, it is a solved problem. Brandes' 2001 algorithm computes exact betweenness for every node in $O(V \cdot E)$ time, so we can find these hidden brokers in networks with millions of members. The next time you wonder who really holds a community together, follow the shortest paths — and watch the brokers light up.