Introduction

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.

Light Up the Brokers

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">A small friendship network. Press <b>Compute betweenness</b> — each node
fills with color in proportion to how often it lies on the shortest paths between every
other pair. The brightest nodes are the <b>brokers</b>. Cut the bridge and watch the
network fragment.</p>
<svg id="net" viewBox="0 0 420 260" role="img" aria-label="friendship network"></svg>
<div class="status" id="status">Press "Compute betweenness".</div>
<div class="btns">
  <button id="compute" type="button">Compute betweenness</button>
  <button id="bridge" type="button">Cut the bridge</button>
  <button id="reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Betweenness centrality: for every ordered pair (s,t), what fraction of the
// shortest paths between them passes through node v? Summed over all pairs, that
// is v's betweenness. We compute it exactly with Brandes' accumulation (2001): a BFS from each source, then a backward sweep adding dependencies. This is a SOLVED problem — O(V*E) for unweighted graphs.

// Two clusters (left A,B,C,D  /  right F,G,H,I) joined by a single bridge E.
const NODES = [
  {id:'A', x: 60, y: 60}, {id:'B', x: 60, y:150}, {id:'C', x:120, y:105},
  {id:'D', x:120, y:200}, {id:'E', x:210, y:130}, {id:'F', x:300, y:105},
  {id:'G', x:360, y: 60}, {id:'H', x:360, y:150}, {id:'I', x:300, y:200}
];
let EDGES = [
  ['A','B'],['A','C'],['B','C'],['B','D'],['C','D'],
  ['C','E'],            // bridge half (left -> E)
  ['E','F'],            // bridge half (E -> right)
  ['F','G'],['F','H'],['G','H'],['F','I'],['H','I']
];
let cut = false;

function adjacency(){
  const adj = {}; NODES.forEach(n => adj[n.id] = []);
  EDGES.forEach(([u,v]) => {
    if (cut && ((u==='C'&&v==='E')||(u==='E'&&v==='C')||(u==='E'&&v==='F')||(u==='F'&&v==='E'))) return;
    adj[u].push(v); adj[v].push(u);
  });
  return adj;
}

// Brandes' algorithm -> betweenness score per node (undirected, unweighted).
function brandes(){
  const adj = adjacency();
  const ids = NODES.map(n => n.id);
  const bc = {}; ids.forEach(s => bc[s] = 0);
  for (const s of ids){
    const stack = [], pred = {}, sigma = {}, dist = {};
    ids.forEach(w => { pred[w] = []; sigma[w] = 0; dist[w] = -1; });
    sigma[s] = 1; dist[s] = 0;
    const queue = [s];
    while (queue.length){
      const v = queue.shift(); stack.push(v);
      for (const w of adj[v]){
        if (dist[w] < 0){ dist[w] = dist[v] + 1; queue.push(w); }
        if (dist[w] === dist[v] + 1){ sigma[w] += sigma[v]; pred[w].push(v); }
      }
    }
    const delta = {}; ids.forEach(w => delta[w] = 0);
    while (stack.length){
      const w = stack.pop();
      for (const v of pred[w]) delta[v] += (sigma[v] / sigma[w]) * (1 + delta[w]);
      if (w !== s) bc[w] += delta[w];
    }
  }
  // Undirected: each pair counted twice -> halve.
  ids.forEach(s => bc[s] /= 2);
  return bc;
}

function color(t){ // t in [0,1] -> pale blue to vivid amber
  const r = Math.round(255*t + 230*(1-t));
  const g = Math.round(176*t + 240*(1-t));
  const b = Math.round( 32*t + 250*(1-t));
  return 'rgb('+r+','+g+','+b+')';
}

const NS = 'http://www.w3.org/2000/svg';
function render(bc){
  const svg = document.getElementById('net'); svg.innerHTML = '';
  const max = bc ? Math.max(1, ...Object.values(bc)) : 1;
  EDGES.forEach(([u,v]) => {
    const a = NODES.find(n=>n.id===u), b = NODES.find(n=>n.id===v);
    const isBridge = (u==='C'&&v==='E')||(u==='E'&&v==='F');
    const ln = document.createElementNS(NS,'line');
    ln.setAttribute('x1',a.x); ln.setAttribute('y1',a.y);
    ln.setAttribute('x2',b.x); ln.setAttribute('y2',b.y);
    ln.setAttribute('class','edge'+(isBridge&&cut?' cut':''));
    svg.appendChild(ln);
  });
  NODES.forEach(n => {
    const g = document.createElementNS(NS,'g'); g.setAttribute('class','node');
    const c = document.createElementNS(NS,'circle');
    c.setAttribute('cx',n.x); c.setAttribute('cy',n.y); c.setAttribute('r',18);
    if (bc) c.setAttribute('fill', color(bc[n.id]/max));
    g.appendChild(c);
    const t = document.createElementNS(NS,'text');
    t.setAttribute('x',n.x); t.setAttribute('y',n.y-1); t.textContent = n.id;
    g.appendChild(t);
    if (bc){
      const s = document.createElementNS(NS,'text');
      s.setAttribute('x',n.x); s.setAttribute('y',n.y+30);
      s.setAttribute('class','score'); s.textContent = bc[n.id].toFixed(1);
      g.appendChild(s);
    }
    svg.appendChild(g);
  });
}
function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+cls; }

function compute(){
  const bc = brandes();
  let top = null, max = -1;
  for (const k in bc) if (bc[k] > max){ max = bc[k]; top = k; }
  render(bc);
  setStatus(fmt('Top broker: %top% (score %max%). %v%', { top: top, max: max.toFixed(1), v: cut?'Bridge is cut.':'Bridge intact.' }), 'ok');
  console.log('Betweenness:', Object.fromEntries(Object.entries(bc).map(([k,v])=>[k,+v.toFixed(2)])));
}
document.getElementById('compute').addEventListener('click', compute);
document.getElementById('bridge').addEventListener('click', ()=>{ cut = !cut; render(null); setStatus(cut?'Bridge cut — recompute to see the fragments.':'Bridge restored.', cut?'bad':''); });
document.getElementById('reset').addEventListener('click', ()=>{ cut = false; render(null); setStatus('Press "Compute betweenness".',''); });
render(null);
Result
Console

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.

The Real Complexity

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(V3)O(V^{3}) time and even O(V2)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⋅E)O(V \cdot E) time on unweighted graphs (and O(V⋅E+V2⋅log⁡V)O(V \cdot E + V^{2} \cdot \log V) with weights), using only O(V+E)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.

Where It Matters

"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.

Conclusion

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⋅E)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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/betweenness-centrality/Content licensed under CC BY-NC 4.0.