The recursive idea

The opener gave the one-liner: a link is a vote, and votes from important pages count more. PageRank is what happens when you take that sentence literally and refuse to let the recursion bottom out. A page's importance is defined in terms of the importance of the pages linking to it - which are themselves defined the same way. That is either circular nonsense or an eigenvector problem, and it turns out to be the latter.

The clean way to think about it is the random surfer. Imagine someone who starts on a random page and, at each step, clicks a uniformly random link on the current page. Let them wander forever. PageRank is the long-run fraction of time they spend on each page - the stationary distribution of that walk. Important pages are simply the ones a random walk keeps returning to.

The web as a matrix

Encode the link graph as an N × N matrix M, where column j describes where the surfer goes from page j. If page j has L(j) outbound links, each target i gets an equal share:

M[i][j] = 1 / L(j)   if j links to i
        = 0          otherwise

Each column sums to 1 - it is a probability distribution over "where a click from page j lands." That makes M column-stochastic, and the whole method rests on that property. A worked four-page graph, with A→{B,C}, B→C, C→A, D→C:

        from:  A    B    C    D
  to A [        0    0    1    0  ]
  to B [       1/2   0    0    0  ]
  to C [       1/2   1    0    1  ]
  to D [        0    0    0    0  ]

Column A splits its weight between B and C; columns B, C, D each send their full weight to a single page. Note column D already hints at trouble - D links out, but nothing links back to it, and no page here is a dead end yet. Hold that thought for section 05.

The rank vector as a fixed point

Let r be the rank vector - one entry per page, summing to 1. The surfer's distribution after one step is M·r. The stationary distribution is the one that no longer changes when you take a step:

r = M · r

That is precisely the statement that r is an eigenvector of M with eigenvalue 1. Because M is column-stochastic, the Perron-Frobenius theorem guarantees such an eigenvector exists and, under the right conditions (section 06), that it is unique and non-negative. So "compute PageRank" reduces to "find the dominant eigenvector of a stochastic matrix." The only question left is how to find it for a matrix with billions of rows - and you do not do it by solving a characteristic polynomial.

Power iteration, concretely

The dominant eigenvector of a stochastic matrix is exactly what power iteration converges to: start with any distribution and multiply by M repeatedly. Each multiply is one step of the random walk applied to the whole distribution at once.

function pagerank(M, N, d = 0.85, eps = 1e-9) {
  let r = new Array(N).fill(1 / N);        // start uniform
  for (let iter = 0; iter < 100; iter++) {
    const next = new Array(N).fill((1 - d) / N);  // teleport term
    for (let j = 0; j < N; j++) {
      for (const i of outLinks[j]) {
        next[i] += d * r[j] / outLinks[j].length; // follow a link
      }
    }
    const delta = next.reduce((s, v, i) => s + Math.abs(v - r[i]), 0);
    r = next;
    if (delta < eps) break;                // converged
  }
  return r;
}

Run the pure r = M·r version (ignore the teleport term for a moment) on the four-page graph and the ranks settle within a dozen iterations to roughly A ≈ 0.4, B ≈ 0.2, C ≈ 0.4, D ≈ 0: C is high because everything funnels into it, A is high because C's entire weight flows back to it, and D collapses to zero because no one links to it. The numbers are the walk's occupancy, read straight off the graph's shape.

Two ways the naive version breaks

The clean r = M·r only behaves on a strongly connected graph. The real web is neither, and two structural pathologies wreck the naive iteration:

  • Dangling nodes. A page with no outbound links (a PDF, a leaf page) is an all-zero column - its probability mass vanishes each step instead of flowing onward. Total rank leaks toward zero, and the vector stops summing to 1.
  • Spider traps and rank sinks. A set of pages that link only among themselves absorbs the surfer forever. In the limit the entire distribution piles onto the trap and every page outside it goes to zero, regardless of merit.

Both are the same failure at root: the Markov chain is reducible or periodic, so Perron-Frobenius does not apply and there is no unique, meaningful stationary distribution to converge to. The fix has to make the chain irreducible and aperiodic - and it is one line.

The damping factor

Give the surfer an escape hatch: at each step, with probability d they follow a link as before, and with probability (1 − d) they teleport to a page chosen uniformly at random. That single change is the full PageRank equation:

r = d · M · r + (1 - d)/N · 1

with d ≈ 0.85 - a random jump roughly every six or seven clicks. The teleport term (1 − d)/N · 1 adds a small uniform probability of reaching every page from anywhere, which makes the chain irreducible (every page reachable from every other) and aperiodic. Perron-Frobenius now guarantees a unique positive stationary vector, and power iteration converges to it from any start.

It also dissolves both pathologies at once. Dangling nodes are handled by redistributing their mass through the teleport (equivalently, treating a dead-end column as linking to everyone); spider traps leak their captured mass back out via the jump. The damping factor is not a tuning knob bolted on for taste - it is the term that makes the problem well-posed.

Convergence and scale

Why this is tractable on a graph of tens of billions of nodes comes down to two facts:

  • The error shrinks geometrically at rate d. The second eigenvalue of the Google matrix is bounded by d, so each iteration cuts the error by ~0.85. Reaching useful precision takes on the order of 50-100 iterations - independent of graph size.
  • Each iteration is a sparse matrix-vector product. M has one nonzero per link, not per page-pair, so a full pass costs O(edges), not O(N²). The average page links to a few dozen others, so edges scale linearly with pages.

At web scale you never materialize M. You stream the link graph, partition pages across machines, and exchange only the rank contributions crossing partitions each iteration - the computation that MapReduce was, in part, built to run. The dangling-mass and teleport terms are global scalars folded in per iteration, so the whole thing stays a handful of linear passes over the edge list.

PageRank's place today

Two clarifications that matter at this level. First, PageRank is query-independent: it scores a page's standing in the graph, computed ahead of time, with no knowledge of any search term. It enters ranking as one prior among the many query-dependent signals from the opener - never the whole score. The toolbar PageRank number Google once exposed has been gone for years; the signal inside has not.

Second, the idea generalized far beyond web search. Topic-sensitive and personalized PageRank bias the teleport vector toward a chosen set of pages instead of a uniform jump - the same math, a different 1 - and the eigenvector-centrality framing now shows up in recommendation systems, citation analysis, and graph databases. What began as a way to rank the authority signal in SEO basics turned out to be a general answer to "which nodes in this graph matter most." That is why it is worth knowing to the matrix, not just the metaphor.

References