What you're seeing
Imagine a surfer clicking links at random forever. From the current page it follows one of the outgoing links with probability d (the damping factor, ~0.85), and with probability 1 − d it gets bored and jumps to a random page. PageRank is the fraction of time the surfer spends on each page in the long run — a page is important if important pages link to it. The nodes start equally sized (rank 1/n); each iteration pushes rank along the links, and you watch the sizes settle: the well-linked hubs swell, the dead ends shrink.
The rule
r = uniform (1/n each)
repeat:
r'[i] = (1−d)/n # teleport: land anywhere
+ d · Σ over j→i of r[j]/outdeg(j) # inherit rank from linkers
(dangling pages with no links spread their rank to everyone)
r = r'
until r stops changing
Each page hands its rank to the pages it links to, split evenly; teleportation keeps the chain well-behaved (no rank vanishes into dead ends or sink cliques).
The invariant
That update is multiplication by the Google matrix P = d·M + (1−d)/n·𝟙 (a column-stochastic transition matrix), and PageRank is its stationary distribution: the rank vector r is a probability distribution (entries ≥ 0, summing to 1) that one more surfing step leaves unchanged, P·r = r. Equivalently, r is the dominant eigenvector of P (eigenvalue 1). It exists and is unique because teleportation makes the chain irreducible and aperiodic (Perron–Frobenius), and power iteration — repeatedly applying P — converges to it geometrically, at rate d per step (which is why higher damping converges more slowly; watch the iteration count climb as you raise d). The teleport term is doing real work: without it, rank would leak into pages with no out-links and the limit wouldn't be a proper distribution.
The cost
Each iteration is one sparse pass over the links — O(edges), not O(n²), because the link matrix is sparse (most pages link to few others). Convergence to a fixed tolerance takes a number of iterations that grows with the damping factor but not with the size of the web, so the whole thing is near-linear in the graph — the property that let it scale to billions of pages. Computing it as a literal eigenvector decomposition would be hopeless at that scale; power iteration is what makes it practical.
In the wild
PageRank (Page & Brin, 1998) was the link-analysis core of early Google, the idea that a page's authority comes from who links to it, not just how many — and it remains a textbook example of spectral methods on graphs. Its descendants are everywhere: personalized / topic-sensitive PageRank for recommendations, EigenTrust for peer-to-peer reputation, citation-impact measures (Eigenfactor), influence ranking in social networks, and even GeneRank in bioinformatics. Any time "importance flows along a graph and you want the steady state," you're looking at PageRank.
Try this
Raise the Damping toward 95% and watch convergence take more iterations — the surfer wanders longer before settling, so the power iteration mixes more slowly. Generate a few New graphs and notice the rank concentrates on the pages many others point to, even indirectly — authority flows through the whole link structure, not just direct links.
References
- Page, L., Brin, S., Motwani, R. & Winograd, T. "The PageRank Citation Ranking: Bringing Order to the Web." Stanford InfoLab Technical Report SIDL-WP-1999-0120, 1999.
- Langville, A. & Meyer, C. Google's PageRank and Beyond: The Science of Search Engine Rankings. Princeton, 2006.
- Spielman, D. Spectral and Algebraic Graph Theory (Yale) — random walks on graphs. cs.yale.edu/homes/spielman/sagt.
- Andoni, A. Advanced Algorithms (Columbia COMS 4995-8, 2021), random-walks lectures. course materials.