The idea: the random surfer
Imagine someone who browses the web without a goal. On every page they click one of its links at random. Now and then they get bored and type in the address of a random page instead. Run this for a long time and count how often they land on each page. That share of time is the page's PageRank. A page is important when many pages link to it, and more so when those pages are important themselves.
Rank flows along links
The same number can be computed without a surfer. Start every page with rank 1/N. In one round, every page splits its rank equally over its out-links, and every page adds up what arrives. With the damping factor d, the probability of clicking rather than jumping:
PR(p) = (1 − d) / N + d · Σ PR(q) / out(q)
q links to p
With N = 5 and d = 0.85 the teleport share is 0.15 / 5 = 0.030. In the first round A has two links and sends 0.100 down each. C receives 0.100 from A, 0.100 from B and 0.100 from D, so its new rank is 0.030 + 0.85 × 0.300 = 0.285 (Demo: one iteration, rank flows along links). The ranks always add up to 1: rank is moved around, never created.
Power iteration
Repeating the round is called power iteration: the vector of ranks is multiplied by the same matrix again and again. The change Σ|Δ| shrinks by about a factor d each round, so the ranks settle. On the sample web the change falls below 0.001 after 10 rounds, with A 0.325, C 0.289, B 0.168, D 0.116 and E 0.101 (Demo: power iteration converges in 10 rounds). The result is the eigenvector of that matrix for eigenvalue 1.
The random surfer gives the same numbers by counting. After 5,000 clicks the share of visits on each page is within one percentage point of its rank (A 32.0% against 0.325, E 10.7% against 0.101) (Demo: random surfer ≈ PageRank). The surfer is a Markov chain over the pages, and PageRank is its stationary distribution.
Dangling pages
A page with no out-links, such as a PDF or an image, is a dangling page. Its rank has no link to flow along and would leak out of the system. The usual fix treats it as linking to every page: its rank is spread evenly over all N pages, just as the surfer jumps to a random page when stuck. Remove the link E→D and D, which nobody links to, falls to 0.053 (Demo: dangling page E).
Spider traps and the damping factor
A spider trap is a group of pages that link only to each other. Rank flows in and never comes out. Without teleport (d = 1) the trap D ↔ E ends with 0.499 each after 22 rounds and A, B and C end with almost nothing (Demo: spider trap, d = 1 swallows all rank). With d = 0.85, 15% of all rank is handed out evenly every round, so the trap still wins (D 0.382, E 0.354) but A, B and C keep 0.081, 0.064 and 0.119 (Demo: d = 0.85 tames the spider trap).
| Graph | d | Rounds | Final ranks A, B, C, D, E |
|---|---|---|---|
| small web | 0.85 | 10 | 0.325, 0.168, 0.289, 0.116, 0.101 |
| dangling page E | 0.85 | 10 | 0.326, 0.192, 0.295, 0.053, 0.134 |
| spider trap D ↔ E | 1 | 22 | 0.000, 0.000, 0.001, 0.499, 0.499 |
| spider trap D ↔ E | 0.85 | 14 | 0.081, 0.064, 0.119, 0.382, 0.354 |
A smaller d (try 0.5) converges faster but listens less to the links: the ranks move towards 1/N. Brin and Page used d = 0.85. Groups of pages that trap rank are the strongly connected components with no edge leaving them.
At web scale
The real graph has billions of pages, but the round is the same: one pass over all links, adding shares into an array. It is a sparse matrix times a vector, easy to split over many machines, and a few dozen rounds are enough. Ranking a search result then mixes PageRank with how well the page matches the words (see BM25 vs vector search).
What the page leaves out
Personalized PageRank (teleport only to chosen pages), topic-sensitive and weighted links, HITS (hubs and authorities), link spam and how search engines fight it, the sparse matrix layout and the distributed computation, and how modern search mixes hundreds of signals besides PageRank.
See where this page fits on the Graph Algorithms mind map.