Introduction

How important is a node in a network? The blunt answer is: count how many other nodes can reach it. But not all paths are equal — a node reachable through a long chain of strangers feels less connected than one a single handshake away.

In 1953, sociologist Leo Katz captured this intuition with a formula. Every path of length kk from any node to a target contributes αk\alpha^{k} to that target's score, where 0<α<10 < \alpha < 1 is a small attenuation factor. Short, direct links count almost in full; longer paths fade geometrically.

Sum over all path lengths and you get the Katz centrality — a single number that weighs a node's entire reachable neighborhood, discounted by distance. It is closed-form, computable from the adjacency matrix, and the direct ancestor of PageRank (which adds the constraint that influence is shared among a node's out-edges rather than broadcast to all).

Try It

The graph below has six nodes. Click any edge button to toggle that connection on or off and watch the Katz scores update instantly. The bar next to each node shows its score relative to the highest-scoring node.

<!-- Katz Centrality demo — interactive graph with live score bars -->
<p class="hint">Toggle edges on/off and drag the α slider to see how Katz scores change. Higher α = more weight on distant paths.</p>
<div id="main-area">
  <canvas id="graph-canvas" width="340" height="260"></canvas>
  <div id="scores-panel">
    <div class="panel-title">Katz scores</div>
    <div id="score-bars"></div>
  </div>
</div>
<div class="controls">
  <div class="alpha-row">
    <label for="alpha-slider">α = <span id="alpha-val">0.20</span></label>
    <input id="alpha-slider" type="range" min="5" max="45" value="20" step="1">
  </div>
  <div id="edge-btns"></div>
</div>
<div class="status" id="status">Scores ready.</div>

/* Layout and node/bar colours for the Katz centrality demo */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
#main-area { display: flex; gap: 12px; align-items: flex-start; flex-wrap: wrap; }
#graph-canvas { border: 1px solid #cdd9e3; border-radius: 10px; background: #f8fafc; flex-shrink: 0; }
#scores-panel { flex: 1; min-width: 140px; }
.panel-title { font-size: .78rem; font-weight: 700; color: #555; text-transform: uppercase; letter-spacing: .05em; margin-bottom: 6px; }
.score-row { display: flex; align-items: center; gap: 6px; margin-bottom: 5px; font-size: .82rem; }
.score-label { width: 22px; font-weight: 700; color: #1d3557; }
.score-bar-wrap { flex: 1; background: #e4ecf3; border-radius: 4px; height: 12px; overflow: hidden; }
.score-bar { height: 100%; background: #457b9d; border-radius: 4px; transition: width .25s; }
.score-num { width: 38px; text-align: right; color: #444; font-size: .78rem; }
.controls { margin-top: 8px; }
.alpha-row { display: flex; align-items: center; gap: 8px; margin-bottom: 6px; font-size: .85rem; }
.alpha-row label { white-space: nowrap; }
#alpha-slider { flex: 1; }
#edge-btns { display: flex; flex-wrap: wrap; gap: 5px; }
.edge-btn { font: 600 12px system-ui, sans-serif; padding: .3rem .55rem;
            border: 1px solid #adb1b8; background: #e2e5ea;
            color: #333; border-radius: 6px; cursor: pointer; transition: all .15s; }
.edge-btn.on { background: #1d3557; border-color: #1d3557; color: #fff; }
.status { font-size: .88rem; font-weight: 600; margin-top: 6px; min-height: 1.3em; color: #555; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Katz centrality via 80-step power iteration — exact for this graph size

// Six labelled nodes with fixed canvas positions
const NODES = [
  { id: 0, label: 'A', x: 60,  y: 50  },
  { id: 1, label: 'B', x: 170, y: 30  },
  { id: 2, label: 'C', x: 280, y: 70  },
  { id: 3, label: 'D', x: 60,  y: 190 },
  { id: 4, label: 'E', x: 170, y: 210 },
  { id: 5, label: 'F', x: 290, y: 180 }
];
const N = NODES.length;

// All possible edges (index = button id)
const ALL_EDGES = [
  [0,1],[1,2],[2,5],[3,4],[4,5],[0,3],[1,4],[2,4],[1,5],[0,4]
];
// Indices of currently active edges
const active = new Set([0,1,2,3,4,5]);

const canvas = document.getElementById('graph-canvas');
const ctx = canvas.getContext('2d');
const R = 18; // node circle radius in pixels

// Compute Katz centrality: x = (I - alpha*A)^-1 * 1 - 1
function katzScores(alpha) {
  // Build adjacency matrix from active edges
  const A = Array.from({length:N}, () => new Float64Array(N));
  for (const i of active) {
    const [u,v] = ALL_EDGES[i];
    A[u][v] = 1; A[v][u] = 1;
  }
  // Power iteration converges because alpha < 1/lambda_1
  // x^(t+1) = alpha * A * x^(t) + 1
  let x = new Float64Array(N).fill(0);
  for (let iter = 0; iter < 80; iter++) {
    const nx = new Float64Array(N).fill(1);
    for (let u = 0; u < N; u++)
      for (let v = 0; v < N; v++)
        nx[u] += alpha * A[u][v] * x[v];
    x = nx;
  }
  // Subtract 1 to match the standard Katz formula
  for (let i = 0; i < N; i++) x[i] -= 1;
  return x;
}

function getAlpha() { return parseInt(document.getElementById('alpha-slider').value, 10) / 100; }

function drawGraph(scores) {
  ctx.clearRect(0, 0, canvas.width, canvas.height);
  const max = Math.max(...scores, 0.001);
  // Draw active edges first so nodes appear on top
  for (const i of active) {
    const [u,v] = ALL_EDGES[i];
    ctx.beginPath();
    ctx.moveTo(NODES[u].x, NODES[u].y);
    ctx.lineTo(NODES[v].x, NODES[v].y);
    ctx.strokeStyle = '#bcc8d4';
    ctx.lineWidth = 2;
    ctx.stroke();
  }
  // Draw nodes coloured by relative score
  for (let i = 0; i < N; i++) {
    const n = NODES[i];
    const t = scores[i] / max;
    ctx.beginPath();
    ctx.arc(n.x, n.y, R, 0, 2*Math.PI);
    const r = Math.round(29 + (69 - 29)*t);
    const g = Math.round(85 + (123 - 85)*t);
    const b = Math.round(87 + (157 - 87)*t);
    ctx.fillStyle = `rgb(${r},${g},${b})`;
    ctx.fill();
    ctx.strokeStyle = '#1d3557';
    ctx.lineWidth = 1.5;
    ctx.stroke();
    ctx.fillStyle = '#fff';
    ctx.font = 'bold 13px system-ui,sans-serif';
    ctx.textAlign = 'center';
    ctx.textBaseline = 'middle';
    ctx.fillText(n.label, n.x, n.y);
  }
}

function updateScoreBars(scores) {
  const max = Math.max(...scores, 0.001);
  const panel = document.getElementById('score-bars');
  panel.innerHTML = '';
  for (let i = 0; i < N; i++) {
    const pct = Math.round((scores[i] / max) * 100);
    const row = document.createElement('div');
    row.className = 'score-row';
    row.innerHTML =
      `<span class="score-label">${NODES[i].label}</span>` +
      `<span class="score-bar-wrap"><span class="score-bar" style="width:${pct}%"></span></span>` +
      `<span class="score-num">${scores[i].toFixed(2)}</span>`;
    panel.appendChild(row);
  }
}

function update() {
  const alpha = getAlpha();
  const scores = katzScores(alpha);
  drawGraph(scores);
  updateScoreBars(scores);
  const top = NODES[scores.indexOf(Math.max(...scores))].label;
  document.getElementById('status').textContent = i18nFmt('Top node: %node% (α = %alpha%)', { node: top, alpha: alpha.toFixed(2) });
}

// Create toggle buttons for every possible edge
const btnArea = document.getElementById('edge-btns');
ALL_EDGES.forEach(([u,v], i) => {
  const btn = document.createElement('button');
  btn.className = 'edge-btn on';
  btn.textContent = `${NODES[u].label}–${NODES[v].label}`;
  btn.title = i18nFmt('Toggle edge %u%–%v%', { u: NODES[u].label, v: NODES[v].label });
  btn.addEventListener('click', () => {
    if (active.has(i)) active.delete(i); else active.add(i);
    btn.className = 'edge-btn' + (active.has(i) ? ' on' : '');
    update();
  });
  btnArea.appendChild(btn);
});

document.getElementById('alpha-slider').addEventListener('input', () => {
  document.getElementById('alpha-val').textContent = getAlpha().toFixed(2);
  update();
});

update();
Result
Console

Notice how adding a single edge can ripple through scores across the entire graph — a node gains not just from its new direct neighbor but from every node reachable through that neighbor, faded by distance. That cascading discount is the essence of Katz centrality, and exactly what PageRank refines further.

The Real Complexity

Katz centrality looks deceptively simple, but computing it exactly or efficiently raises real questions.

The closed-form formula. Let AA be the adjacency matrix and 1\mathbf{1} a vector of ones. The Katz score vector is:

x=(I−αA)−11−1\mathbf{x} = (I - \alpha A)^{-1}\mathbf{1} - \mathbf{1}

This works as long as α<1/λ1\alpha < 1/\lambda_{1}, where λ1\lambda_{1} is the largest eigenvalue of AA. If α\alpha is too large, the geometric series of path counts diverges.

Complexity. Direct matrix inversion costs O(n3)O(n^{3}) for nn nodes. For dense graphs with thousands of nodes that is fine; for social or web graphs with millions of nodes it is hopeless.

Power iteration. Instead, note that (I−αA)x=1(I - \alpha A)\mathbf{x} = \mathbf{1} can be solved iteratively: start from x(0)=0\mathbf{x}^{(0)} = \mathbf{0} and repeat x(t+1)=αAx(t)+1\mathbf{x}^{(t+1)} = \alpha A \mathbf{x}^{(t)} + \mathbf{1}. Each step costs O(∣E∣)O(|E|) for a sparse graph, and convergence is geometric in αλ1\alpha\lambda_{1}. This is exactly how PageRank is computed in practice.

The attenuation constraint. Choosing α\alpha is not free. Too large and the series diverges; too small and only immediate neighbors matter. In practice α\alpha is set to a fraction of 1/λ11/\lambda_{1}, balancing reach against stability.

Where It Matters

The idea of discounted path counts appears everywhere a node's influence must be measured across a network:

  • Citation and academic impact: a paper cited by highly cited papers inherits some of their prestige — exactly the Katz logic. Variants drive h-index refinements and journal impact measures.
  • Social influence ranking: who can a message reach in two hops? Three hops? Katz centrality weights all of these, making it richer than degree (one hop) or closeness (shortest path only).
  • Recommendation systems: in a user–item bipartite graph, Katz scores surface items that many users, who are themselves well-connected, have interacted with.
  • Biological networks: protein–protein interaction networks use Katz-style scores to find proteins that are central to many pathways, even if they are not directly the most connected.
  • The PageRank connection: Google's original PageRank is Katz centrality with one modification — influence from a node is divided equally among its out-links rather than broadcast. Understanding Katz makes PageRank immediately transparent.

Conclusion

Leo Katz set out to measure social status in small groups. His answer — sum every path to a node, shrink longer ones by αk\alpha^{k} — turned out to be one of the most reusable ideas in all of network science.

Decades later, Brin and Page refined it into PageRank, dividing a node's influence among its out-links instead of broadcasting it. But the core intuition is Katz's: not just who connects to you, but who connects to those who connect to you, fading with each extra step.

Next time you search the web, you are benefiting from a discount factor invented for a 1953 sociometry paper.

Share this article

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

Comments

Loading comments...

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