Eigenvector Centrality, in depth: the Perron-Frobenius conditions, shifted power iteration, a worked six-node example and where the measure breaks

The definition and why it is an eigenvector

Let A be the adjacency matrix of an undirected graph with n nodes, so A[i][j] = 1 when i and j are connected, or the edge weight. We want scores x where each node's score is proportional to the sum of its neighbours' scores:

x_i = (1 / lambda) * sum_j A[i][j] * x_j        for every node i
       which in matrix form is       A x = lambda x

The constant lambda is needed because without it the only solution is x = 0. The equation says x is an eigenvector of A. A has n eigenvectors, so which one? We want scores that are all positive, so that more connections never make a node look worse, and the Perron-Frobenius theorem says that for a non-negative matrix of a connected graph exactly one eigenvector has that property: the one for the largest eigenvalue lambda1. Its entries are all strictly positive and it is unique up to scale. Eigenvector centrality is that vector, usually scaled to unit Euclidean length or so that the largest entry is 1.

For directed graphs there is a choice. With A[i][j] meaning an edge from i to j, the common convention, used by networkx, is that a node's score comes from the nodes pointing at it, so x is the leading eigenvector of A transposed. A web page is important if important pages link to it, not because it links to them. State which convention you use, because the other one answers a different question.

Worked example: two nodes of equal degree

Take the graph above with edges A-B, A-C, B-C, C-D, D-E and D-F. C and D both have degree 3, so degree centrality cannot separate them. Start every node at 1 and apply x ← A x, summing neighbours' scores:

Iteration 1 is just degree. At iteration 2 C pulls ahead: its neighbours A and B have degree 2 each and D has 3, while D's neighbours E and F have degree 1. Iteration k counts walks of length k ending at each node, so the leading eigenvector measures how many long walks reach a node. The raw numbers grow like lambda1 to the power k, which is why real implementations normalise every step.

The converged values satisfy the definition. The largest eigenvalue is lambda1 = 2.2784, and for C the neighbours' sum is 0.457 + 0.457 + 0.417 = 1.331, and 1.331 / 2.2784 = 0.584. For E, 0.417 / 2.2784 = 0.183. Ranking by score gives C, then A and B, then D, then E and F: D has as many connections as C but they lead nowhere.

Power iteration and the shift

Power iteration computes the leading eigenvector by repeated multiplication. Write the start vector as a combination of eigenvectors, x0 = c1 v1 + c2 v2 + ... + cn vn. After k multiplications, each component is scaled by its eigenvalue to the power k, so the vi component shrinks relative to v1 by (lambda_i / lambda1) to the power k. As long as c1 is not zero, which a positive start vector guarantees, the iterates line up with v1.

The speed depends on the second-largest eigenvalue in absolute value, not just the second largest. Our graph has eigenvalues 2.278, 1.317, 0, -0.705, -1 and -1.891. The negative one at -1.891 is the bottleneck: the error shrinks by 1.891 / 2.278 = 0.83 per step, and iterating on A until the L1 change is under 6e-6 takes 61 steps.

The fix is a shift. Iterating with A + I adds 1 to every eigenvalue without changing the eigenvectors, giving 3.278, 2.317, ..., -0.891. Now the worst ratio is 2.317 / 3.278 = 0.71, and the same tolerance is reached in 31 steps. The networkx implementation of eigenvector_centrality iterates with A + I for this reason, as a comment in its source says.

The shift also fixes a worse problem. In a bipartite graph the spectrum is symmetric, so -lambda1 is also an eigenvalue and power iteration on A never converges; on a star with one centre and three leaves, starting from the centre, the vector flips between the centre and the leaves forever. With A + I the negative eigenvalue becomes 1 - lambda1, smaller in magnitude than 1 + lambda1, and the iteration converges.

Implementation and tests

The implementation below works on a SciPy sparse matrix, so each step costs O(n + m) for n nodes and m edges. It uses the in-edge convention for directed graphs, the A + I shift, the same L1 stopping rule as networkx (total change under n times tol), and it refuses inputs where the answer is not well defined.

import numpy as np
import scipy.sparse as sp
from scipy.sparse.csgraph import connected_components

def eigenvector_centrality(A, tol=1e-6, max_iter=1000):
    """A: square sparse matrix, A[i, j] = weight of edge i -> j (symmetric if undirected).
    Returns (x, lambda1, iterations); x has unit Euclidean norm and positive entries."""
    A = sp.csr_matrix(A, dtype=float)
    n = A.shape[0]
    if A.nnz == 0:
        raise ValueError("graph has no edges")
    if (A.data < 0).any():
        raise ValueError("negative weights break Perron-Frobenius")
    k, _ = connected_components(A, directed=True, connection="strong")
    if k > 1:
        raise ValueError(f"{k} strongly connected components; score each one or use Katz/PageRank")
    AT = A.T.tocsr()                       # score flows along edges: x_j gets x_i for i -> j
    x = np.full(n, 1.0 / np.sqrt(n))
    for it in range(1, max_iter + 1):
        y = AT @ x + x                     # (A^T + I) x
        y /= np.linalg.norm(y)
        if np.abs(y - x).sum() < n * tol:
            lam = y @ (AT @ y)             # Rayleigh quotient estimate of lambda1
            return y, lam, it
        x = y
    raise RuntimeError(f"no convergence in {max_iter} iterations")

Test it against a dense eigensolver on small random graphs, which is the cheapest way to catch convention errors:

rng = np.random.default_rng(0)
for trial in range(200):
    n = int(rng.integers(5, 40))
    M = (rng.random((n, n)) < 0.25).astype(float)
    M = np.triu(M, 1); M = M + M.T                  # undirected, no self loops
    if connected_components(M, directed=False)[0] > 1:
        continue
    x, lam, _ = eigenvector_centrality(M, tol=1e-10)
    w, V = np.linalg.eigh(M)
    v = np.abs(V[:, -1])                             # sign of an eigenvector is arbitrary
    assert np.allclose(x, v / np.linalg.norm(v), atol=1e-6)
    assert abs(lam - w[-1]) < 1e-6
print("ok")

Note the absolute value. Eigensolvers return an eigenvector with an arbitrary sign, and the leading one often comes back all negative. Flip it so that the entries sum to a positive number before using it as a score.

When the eigenvector misleads

The Perron-Frobenius guarantee needs the graph to be connected, or for directed graphs strongly connected, meaning every node can reach every other. When that fails the results mislead quietly, and it is worth knowing what each case does. The behaviour below was measured with a reimplementation of the networkx loop at its default of 100 iterations.

• Directed acyclic graphs. Every eigenvalue of a DAG's adjacency matrix is 0, so there is no meaningful leading eigenvector. On the chain a → b → c → d, the shifted iteration piles weight onto the sink and the scores are still changing at iteration 100 (d at 0.9995, c at 0.03), so networkx raises PowerIterationFailedConvergence. Citation graphs and dependency graphs are nearly acyclic; do not use this measure on them.
• Sources. A node with no incoming edges gets 0, however many nodes it points at. A source feeding a three-node cycle converges with the source effectively at 0; its true eigenvector value is 0, and the shifted iteration only decays towards it.
• Several strongly connected components. When one cycle feeds another, weight drains downstream: upstream nodes decay towards 0 and the iteration again fails to converge in 100 steps. Disconnected undirected graphs behave similarly, with the component of largest lambda1 taking everything, so scores in different components are not comparable. Find components first with Tarjan's algorithm and score each one separately.
• Hub localisation. In large sparse graphs with a few very high-degree nodes, the leading eigenvector can concentrate almost all its weight on one hub and its immediate neighbours, leaving the rest of the graph with near-zero scores that rank essentially at random. Martin, Zhang and Newman (2014) analysed this and proposed a non-backtracking variant that avoids it. Check for it by measuring how much of the squared norm sits on the top 1 percent of nodes.

Katz centrality and PageRank

Two variants fix the existence problems by adding a constant to every node, and are the right choice for directed graphs in practice.

Katz with alpha close to 1/lambda1 approaches eigenvector centrality; with small alpha it approaches in-degree. PageRank's normalisation means a node that links to thousands of others passes on little to each, which eigenvector centrality does not do. For an undirected, connected social or co-occurrence graph, eigenvector centrality is fine and has no parameters, which is a real advantage.

Related machinery appears elsewhere: walk counting is the same matrix powering as in matrix exponentiation, and for graph-based retrieval the scores are a cheap way to rank entities, as in graph RAG architectures.

Scaling to large graphs

Each iteration is one sparse matrix-vector product, so a graph with a billion edges takes a few seconds per iteration on one machine with a compressed sparse row layout, and tens of iterations suffice with the shift. Practical points:

• Build the matrix once in CSR form and keep the transpose; do not loop over a dictionary of neighbours in Python, which is typically one to two orders of magnitude slower.
• For more than a few iterations' worth of accuracy, use an eigensolver such as ARPACK through scipy.sparse.linalg.eigs with which="LR", which networkx's eigenvector_centrality_numpy uses, but flip the sign of the result.
• On a distributed graph engine, the same iteration is a vertex program: each node sends its score along out-edges, sums incoming messages, and a global aggregation computes the norm.
• Use a looser tolerance than you think. Rankings stabilise long before the scores' last digits do; compare top-k sets between iterations and stop when they stop changing.
• If the graph changes, warm-start from the previous scores. A few iterations usually suffice after a small update.

Failure modes

The common mistakes are mostly about the input, not the arithmetic.

• Wrong direction. Using A instead of A transposed scores nodes by whom they point at. Test on a three-node graph where the answer is obvious.
• Self-loops and multi-edges. A self-loop adds to a node's own score every iteration; parallel edges count twice. Decide deliberately whether either belongs in the matrix.
• Weights on very different scales. One edge with weight 10,000 dominates the spectrum. Log-scale or cap weights first.
• Comparing across graphs. Unit-norm scores depend on n; a score of 0.1 means different things in graphs of 100 and 100,000 nodes. Compare ranks or scores divided by the maximum.
• Ignoring the convergence error. A loop that silently returns after max_iter on a DAG produces plausible-looking numbers. Raise on non-convergence, as the code above does.

What to do next

To apply eigenvector centrality to your own graph:

1. Decide the edge direction convention and whether weights, self-loops and multi-edges belong in A.
2. Find connected or strongly connected components, and score each component separately or switch to Katz or PageRank. Breadth-first search from BFS and DFS in depth is enough for undirected graphs.
3. Run shifted power iteration on a sparse matrix, and raise an error on non-convergence.
4. Validate against a dense eigensolver on small samples, taking the absolute value of the reference.
5. Check for localisation by measuring the share of weight on the top 1 percent of nodes.
6. Compare the ranking with degree; where they disagree, inspect a few nodes by hand to confirm the difference makes sense for your question.
7. Report ranks or max-scaled scores, not raw unit-norm values.