Important Because the Important Say So

In the mid-1990s, searching the web mostly meant matching words. Type a phrase and an engine returned pages containing it, ranked largely by how often and how prominently the words appeared. That was easy to cheat, by repeating words in text the reader could not see, and it was no help with the question a searcher actually has, which is not which pages mention this but which of them are any good.

Links looked like an answer. A link is a small act of endorsement: somebody, somewhere, thought a page worth pointing to. So count them. The page with the most incoming links is presumably the most respected.

The trouble is that links are not equal. A link from a page that nobody reads, or from a page created for the purpose, should not count for as much as a link from one that many people trust. But what makes a page trusted? Presumably that trusted pages link to it.

Sergey Brin and Larry Page, then graduate students at Stanford, took that circle and declined to be embarrassed by it. In their 1998 paper describing the prototype of Google, a page's rank is the sum of contributions from every page linking to it, where each linking page contributes its own rank divided equally among all the pages it links to. A page with high rank and few outgoing links passes on a lot to each. A page with low rank, or one that links to everything, passes on little.

That defines every page's rank in terms of other pages' ranks, and it looks viciously circular. It is not, because it is not a recipe to be followed in order. It is a system of equations, one per page, and the ranks are whatever numbers satisfy all of them at once.

A small example shows both how it works and why it is not link counting. Three pages. A links to B and to C. B links to C. C links to A. A receives everything C has, because C links only to A, so A's rank equals C's. B receives half of A's, since A splits its rank between two pages. C receives the other half of A's and all of B's. Solve, with the ranks adding up to one, and A and C each have 0.4 while B has 0.2.

Look at what happened. C has two incoming links and A has only one, and they come out equal, because A's single link comes from the most important page in the system, which gives A everything it has. A and B each have exactly one incoming link, and A's is worth twice as much. Counting links gets this wrong in both directions.

How do you find the numbers for a web of billions of pages? You guess. Give every page the same rank, apply the rule once to get new ranks, apply it again to those, and keep going. The numbers settle down, and a theorem proved by Oskar Perron and Georg Frobenius before the First World War guarantees that, under the right conditions, they settle on one answer whatever you started from.

The right conditions need help. A group of pages that link only to each other would soak up rank and never pass it back, and a web with several such traps can have more than one consistent answer. Brin and Page fixed this with a second picture, the random surfer. Imagine a reader who on each page clicks a link chosen at random, except that some fixed share of the time they get bored and jump to a page chosen at random from the whole web. In their paper the surfer follows a link 85 per cent of the time and jumps the other 15. The long-run share of time this surfer spends on each page is its rank, and the jump guarantees that the answer exists, is unique, and cannot be trapped.

None of this was entirely new, and it is worth saying so. Leo Katz had proposed a measure of status in social networks along similar lines in 1953, and in 1976 Gabriel Pinski and Francis Narin ranked scientific journals by citations weighted according to the influence of the journal doing the citing. What was new was the scale, and then the money.

The money changed the thing being measured. Because the random jump visits every page sometimes, every page has a little rank, even an empty one, and passes it along its links. Build a few hundred pages that exist only to point at your site and you have manufactured endorsement. Link farms followed, and the history of search since has been in part a history of defending the measure from the people it measured.

That is the general lesson, and it reaches well beyond search. A ranking computed from links, citations or recommendations is only as good as the assumption that they were given for their own reasons. The moment the ranking is worth something, that assumption is under attack.