Katz Centrality

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 $k$ from any node to a target contributes $\alpha^{k}$ to that target's score, where $0 < \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).

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.

<!-- {{c_html_intro}} -->
<p class="hint">{{hint_para}}</p>
<div id="main-area">
  <canvas id="graph-canvas" width="340" height="260"></canvas>
  <div id="scores-panel">
    <div class="panel-title">{{panel_title}}</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">{{status_ready}}</div>

/* {{c_css_intro}} */
* { 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; }

// Code not found

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.

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

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

$$\mathbf{x} = (I - \alpha A)^{-1}\mathbf{1} - \mathbf{1}$$

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

Complexity. Direct matrix inversion costs $O(n^{3})$ for $n$ 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 - \alpha A)\mathbf{x} = \mathbf{1}$ can be solved iteratively: start from $\mathbf{x}^{(0)} = \mathbf{0}$ and repeat $\mathbf{x}^{(t+1)} = \alpha A \mathbf{x}^{(t)} + \mathbf{1}$. Each step costs $O(|E|)$ for a sparse graph, and convergence is geometric in $\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/\lambda_{1}$, balancing reach against stability.

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.

Leo Katz set out to measure social status in small groups. His answer — sum every path to a node, shrink longer ones by $\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.