Katz Centrality, in depth: discounted walk counts, the alpha convergence bound, a worked example and scalable code

Definition: counting walks with a discount

Let A be the adjacency matrix of a directed graph, with A[j][i] = 1 when there is an edge from j to i. A classic fact: entry (j, i) of A raised to the power k counts the walks of length k from j to i. Summing over j, the vector (A^T)^k 1 gives, for each node i, the number of length-k walks that end at i. Katz centrality adds these counts over all lengths, discounting length k by alpha to the power k, and adds a baseline beta that every node receives:

x = beta * (alpha A^T + alpha^2 (A^T)^2 + alpha^3 (A^T)^3 + ...) 1  +  beta * 1
  = beta * (I - alpha A^T)^(-1) 1

equivalently, node by node:
x_i = alpha * sum over in-neighbours j of x_j  +  beta

The last line is the useful one. A node's score is a discounted sum of its in-neighbours' scores plus a constant. Compare it with eigenvector centrality, x_i = (1/lambda) * sum_j x_j, which has no constant term. That missing beta is the whole story. In a directed graph, a node with no in-edges gets eigenvector centrality zero, and so does everything downstream that is only reachable from such nodes. In a directed acyclic graph, such as a citation network, eigenvector centrality is zero everywhere. Katz's beta keeps every node alive, so influence can flow from the sources.

Some texts and libraries drop the k = 0 term and report x - beta, and some write the edge direction the other way (counting walks that start at a node, a measure of reach rather than prestige). Neither changes the ranking within one convention, but mixing conventions between two systems produces silent disagreement. Write your convention down.

Convergence and choosing alpha

The series I + alpha A + alpha^2 A^2 + ... converges exactly when alpha times the spectral radius rho(A), the largest absolute eigenvalue, is less than 1. So the hard constraint is 0 < alpha < 1 / rho(A). Above it, walk counts grow faster than alpha shrinks them and the scores blow up; at exactly 1/rho the matrix I - alpha A^T is singular.

Within the allowed range, alpha is a dial between two familiar measures. As alpha approaches 0, the length-1 term dominates and the ranking approaches in-degree. As alpha approaches 1/rho, long walks dominate and, on a strongly connected graph, the ranking approaches eigenvector centrality. Practical choices sit in between; a common default is a fraction of 1/rho, such as 0.5/rho to 0.9/rho, chosen by checking rankings against known-good examples.

You need rho to choose alpha, but you do not need it exactly. Power iteration on A estimates it in a few dozen sparse matrix-vector products. A cheap safe bound needs no iteration at all: rho is at most the largest row sum and at most the largest column sum, so alpha < 1 / max_degree always converges, at the price of possibly being far more conservative than necessary.

Graph structure tells you where rho comes from. Walks can only grow without limit by going round cycles, and every cycle lives inside one strongly connected component. The spectral radius of the whole graph is therefore the largest spectral radius among its strongly connected components, and a directed acyclic graph has rho = 0, so its Katz series is a finite sum that converges for any alpha. Splitting the graph into components first, for example with Gabow's SCC algorithm, lets you estimate rho on the one dense component that matters instead of the whole graph, and it explains surprises: a single new tightly connected cluster can raise rho enough to make yesterday's alpha diverge today.

Worked example: five nodes by hand

Take five nodes and six directed edges: A to C, B to C, B to D, C to D, D to E and E to C. A and B have no incoming edges. C, D and E form a cycle of length 3, and that cycle sets the spectral radius: rho = 1. Choose alpha = 0.5 and beta = 1. The node equations are:

x_A = 1
x_B = 1
x_C = 1 + 0.5 * (x_A + x_B + x_E)
x_D = 1 + 0.5 * (x_B + x_C)
x_E = 1 + 0.5 * x_D

Substituting gives x_C = 23/7 = 3.286, x_D = 22/7 = 3.143 and x_E = 18/7 = 2.571. Check one: x_E = 1 + 0.5 x 22/7 = 1 + 11/7 = 18/7. The ranking C, D, E, then A and B tied, matches intuition: C has three endorsers, D has two (one of them the top node), E has one.

Eigenvector centrality on the same graph gives A and B exactly zero and C, D and E an identical one third each, because on the cycle each node has one in-neighbour inside the cycle. It cannot tell C from E, even though C has three endorsers and E has one. Katz can, because the baseline from A and B flows into C and D.

Iterating the node equations from zero shows how convergence behaves. After one step every node is 1. After two, C is 2.5 and D is 2. The largest change per step falls from 1.5 to 0.75 to 0.375, halving each time, because the error contracts by alpha times rho = 0.5. After 20 steps it is about 6 x 10^-6; after 50 it is at machine precision. With the code in the next section and a tolerance of 10^-10, alpha = 0.5 needs 36 sweeps and alpha = 0.9 needs 230; at alpha = 1.1 the values grow without bound.

Computing it: power iteration in code

For real graphs, store edges in adjacency lists (or compressed sparse rows) and iterate. Each sweep costs O(V + E), and the number of sweeps is about log(tol) / log(alpha * rho).

def spectral_radius(in_nbrs, n, iters=100):
    """Power iteration estimate of rho for a graph given as in-neighbour lists."""
    v = [1.0] * n
    rho = 0.0
    for _ in range(iters):
        w = [sum(v[j] for j in in_nbrs[i]) for i in range(n)]
        norm = max(abs(t) for t in w)
        if norm == 0:
            return 0.0                     # walks die out: the graph is acyclic
        rho, v = norm, [t / norm for t in w]
    return rho


def katz(in_nbrs, alpha, beta=1.0, tol=1e-10, max_iter=10_000):
    n = len(in_nbrs)
    x = [0.0] * n
    for it in range(max_iter):
        new = [beta + alpha * sum(x[j] for j in in_nbrs[i]) for i in range(n)]
        delta = max(abs(a - b) for a, b in zip(new, x))
        x = new
        if delta < tol:
            return x, it + 1
        if delta > 1e12:
            raise ValueError("diverging: alpha is at or above 1/rho")
    raise RuntimeError("no convergence; lower alpha or raise max_iter")


# A, B, C, D, E = 0..4; in-neighbours of each node
g = [[], [], [0, 1, 4], [1, 2], [3]]
rho = spectral_radius(g, 5)            # about 1.0 for this graph
scores, sweeps = katz(g, alpha=0.5)
print([round(s, 3) for s in scores], sweeps)   # [1.0, 1.0, 3.286, 3.143, 2.571]

The power iteration estimate oscillates on graphs whose dominant eigenvalue is complex or shares its modulus with others, which happens on periodic graphs; treat it as an estimate, add a safety margin, and fall back to the degree bound if it fails to settle. In Python at scale, use SciPy sparse matrices and either the same iteration or a sparse linear solver on (I - alpha A^T) x = beta 1. NetworkX ships katz_centrality (power iteration) and katz_centrality_numpy (a direct solve); check its normalisation and edge-direction conventions before comparing numbers.

Scaling and variants

Because each sweep is a sparse matrix-vector product, Katz scales like PageRank. Graphs with billions of edges are handled by partitioning edges across workers and exchanging the score vector each sweep, the same pattern as a vertex-centric graph engine. A few variants are worth knowing.

• Personalised Katz. Replace the constant beta with a vector that is nonzero only for a seed set, such as accounts a user follows. Scores then measure discounted walks from the seeds.
• Truncated Katz. Stop the series at a fixed length K. This is exactly K sweeps, needs no convergence check, and is safe for any alpha. Powers of a matrix can also be computed by repeated squaring for small dense graphs, as in Matrix Exponentiation, in depth.
• Katz for link prediction. The matrix (I - alpha A)^(-1) - I scores pairs of nodes by discounted walks between them, a strong baseline for predicting missing edges.
• Weighted graphs. Use edge weights in A. The convergence bound then uses the weighted spectral radius, which can be much larger than for the unweighted graph.

Failure modes

• Alpha above 1/rho. The iteration diverges, or a direct solver returns large signed numbers without complaint. Always check the sign and size of the result, and recompute rho when the graph grows, because adding edges can only raise it.
• Alpha too small. The result is in-degree with extra steps. Compare the ranking with in-degree; if they agree almost perfectly, alpha is not doing any work.
• Reversed edges. Using A instead of A transpose measures outgoing reach, not incoming prestige. Test on a star graph whose answer you know.
• Hub domination. Unlike PageRank, Katz does not divide a node's influence by its out-degree, so a node that links to everything passes full weight to each target. Spam farms exploit exactly this. Normalise by out-degree if endorsements should be a fixed budget.
• Normalisation hiding drift. Libraries often normalise the vector. Rankings stay correct, but absolute scores from two runs are not comparable unless you fix the normalisation.

Trade-offs against other centralities

Choose Katz when walk counts are meaningful in themselves, such as influence spreading through a network where each extra hop weakens it, and when you want a single dial between local and global importance. Choose PageRank when nodes have a fixed endorsement budget. For grouping rather than ranking, see Label Propagation.

What to do next

1. Write down your edge-direction and normalisation convention before computing anything.
2. Estimate rho with power iteration and pick alpha as a fraction of 1/rho; record the value with the scores.
3. Reproduce the five-node example above with your code and get 3.286, 3.143 and 2.571.
4. Compute rankings at two or three alpha values and compare them with in-degree to see what alpha changes.
5. Add a divergence guard and a convergence check to the production job, and alert on sweep count.
6. If the graph has spam or hubs, compare with an out-degree-normalised variant before shipping rankings.