How a random surfer ranks the web

Imagine a reader who clicks links at random, forever. Most of the time they follow a link on the page in front of them; now and then they get bored and jump to a page picked at random. Ask how often, in the long run, that reader is standing on each page. The answer is a ranking of the whole web, and it is the idea Sergey Brin and Lawrence Page built Google on.

What is being claimed

Brin and Page's 1998 paper defines a page's PageRank as the probability that this random surfer is visiting it. A link counts as a vote, but not all votes weigh the same. A page passes its own rank along its outgoing links, split equally between them. So a link from a page that is itself visited often is worth more, and a link from a page with a hundred other links is worth less than a link from a page with two.

Why it is worth knowing

Counting links is easy to game: make a thousand pages and point them all at yours. PageRank asks where those thousand pages get their own rank, and if nothing important links to them, the answer is from bored jumps alone, which gives each of them very little to pass on. Brin and Page add that aiming the jumps at a single page or a group of pages allows personalization and makes it “nearly impossible to deliberately mislead the system”. Their paper reports maps of as many as 518 million hyperlinks, and says the ranks for 26 million pages can be computed “in a few hours on a medium size workstation”.

The formula, read the right way round

For a page A with incoming links from pages T1 to Tn, the paper writes PR(A) = (1−d) + d(PR(T1)/C(T1) + … + PR(Tn)/C(Tn)), where C(T) is the number of links going out of page T. The damping factor d “can be set between 0 and 1”, and they “usually set d to 0.85”. That is a working choice, not a derived optimum. In the formula, d multiplies the rank that arrives along links, so it is the chance of following a link: 85% of the time the surfer clicks, 15% of the time they jump. The paper's own sentence of explanation says the opposite, calling d the probability that the surfer gets bored. The equation is the one that computes the ranks, so read it as 85/15. With those odds the surfer follows 0.85/0.15, about 5.7, links on average before each jump (our arithmetic, ignoring dead ends).

One more wrinkle: with (1−d) written as it is, the ranks add up to the number of pages rather than to one (on a web with no dead ends), though the paper says they form a probability distribution summing to one. Dividing the (1−d) by the number of pages fixes the total, and a web with dead ends needs the extra step of spreading whatever rank they swallow. The figure below uses the version that sums to one.

Solving a definition that refers to itself

Every page's rank depends on the ranks of the pages linking to it, so there is no obvious place to start. The fix is to start anywhere and repeat. Give every page the same rank, hand each page's rank out along its links, and do it again. Each round is one step of the surfer, averaged over every possible surfer at once. The 1999 technical report by Page and Brin describes the simple version as “the standing probability distribution of a random walk on the graph of the Web”, and stops when the total change between one round and the next, the 1-norm, falls below a tolerance. Brin and Page note the answer is the principal eigenvector of the web's normalized link matrix. The standard name for this setup is a Markov chain, though neither source uses the word.

Why the bored jump is needed

Without it, rank can get stuck. The report describes two pages that link only to each other: once rank flows in, the loop “will accumulate rank but never distribute any rank”. It calls this a rank sink and fixes it with a rank source, a vector E that tops every page up. A page with no links out at all, a dead end, loses rank outright in the figure unless the jumps put it back. The report handles such dangling links by removing them before computing and adding them back afterwards.

It converges quickly. On a database of 322 million links the report finds a reasonable tolerance in roughly 52 iterations, and on half the data roughly 45, which the authors call “roughly linear in log n”: doubling the links cost about seven more rounds (our subtraction). Each iteration took about 6 minutes on a typical workstation, and the whole process about five hours. Neither source says what tolerance it used.

In short

PageRank is where a surfer who clicks 85% of the time and jumps 15% of the time spends their time. A page ranks high when highly ranked pages link to it. Repeating the hand-out until the numbers stop changing finds those ranks, and the jumps keep loops and dead ends from swallowing them.