Imagine a random surfer clicking links on the web. They follow each outgoing link with equal probability; occasionally they teleport to a random page. The long-run probability of being on each page is its PageRank. Mathematically: the dominant eigenvector of a stochastic matrix. Brin and Page, 1998 — the algorithm that built Google.
why PageRank is just the dominant eigenvector
A directed graph: nodes are web pages, edges are links. The "random surfer" walks along edges, picking a random outgoing edge at each step. Occasionally (probability 1−d, typically 1−d = 0.15) they teleport to a uniform random node — this prevents the walker getting stuck in dead ends or cycles.
Mathematically, the surfer's probability distribution after one step is:
p_(t+1) = d · A·p_t + (1−d) · 1/N
where A is the column-stochastic matrix of link probabilities. As t → ∞, p_t converges to the unique fixed point — the eigenvector of d·A + (1−d)/N · J with eigenvalue 1 (J is all-ones matrix). PageRank is this stationary distribution.
Why it works: pages that get many incoming links (especially from already-important pages) accumulate probability. The recursion "a page is important if important pages link to it" is self-consistent only at the eigenvector solution.
The original Google paper (Brin and Page, Stanford 1998): "The Anatomy of a Large-Scale Hypertextual Web Search Engine." PageRank was one of several signals, but it was the breakthrough. With 200 million pages indexed by 1998 and the page-link graph as input, PageRank gave ordered results in seconds. By 2000, Google had become the dominant search engine.
Why "d": without damping, the iteration can fail to converge on graphs with cycles, dead-ends, or disconnected components. The teleportation guarantees the matrix is strongly connected — Perron-Frobenius then guarantees a unique positive eigenvector. d ≈ 0.85 is empirically optimal — it balances stability with influence of the link structure.
Beyond search: PageRank is now used in citation analysis, protein interaction networks, finding bottlenecks in road networks, ranking sports teams, even neural networks for relevance scoring. It's the foundation of centrality in network science.