Pattern · networks · a showing you can run

The Importance That Points at Itself

Which page on the web matters most? Here is an answer that seems to break the moment you say it: a page matters if pages that matter point to it. Read it again — it defines importance in terms of itself. And yet this snake-eating-its-tail has exactly one answer. It is the number Google was built on, and you can watch it arrive three different ways below.

Counting links can't work. If a page were important just for having many pages point at it, anyone could manufacture importance with a thousand junk pages. So the definition has to be recursive: a link from an important page should count more than a link from a nobody. But then to know who's important you first need to know who's important — the circle closes, and it looks hopeless.

It isn't. A circular definition like this is a fixed point: a set of scores that, when you push each page's score out along its links and add up what each page receives, hands back the very same scores. Below is a tiny nine-page web. Press step and watch the scores chase their own tail until they stop moving.

It settles. And once it does, look at the two pages I've labelled: E has a single inbound link; F has three. Yet E ends up more than three times as important as F. E's one link comes from B, the most important page in this little web; F's three links come from G, H and I, three pages nobody points at. Rank flows from who points at you, not how many. That is the whole idea, and you just watched it compute itself.

The same number, wearing two faces

There are two ways to read the settled scores, and they are secretly identical.

The linear-algebra face. "Push scores along links and get the same scores back" is the equation G·r = r — the scores r are an eigenvector of the link matrix G, the one with eigenvalue 1. Instrument 1 found it by the oldest trick in numerical linear algebra: apply G over and over and the eigenvector emerges. That's called power iteration.

The probability face. Imagine a bored surfer who clicks links at random forever. Where does she spend her time? A page she visits often is one that many well-visited pages link to — the same recursive notion. The long-run fraction of time she spends on each page is the score. Turn her loose:

Two processes with nothing in common — a deterministic matrix multiply and one drunkard's walk — arrive at the same vector. A physicist would call it an ergodic Markov chain; either way, importance is where the walk pools.

Two diseases, and the one strange cure

The real web is not a tidy little graph, and the naive rule breaks on it in two ways.

Dead ends. A page that links to nothing — a PDF, an image — is a dangling node. The surfer walks in and can't get out; rank pours in and drains off the edge of the world, and the scores stop adding up to a whole.

Traps. A little clump of pages that only link to each other is a spider trap. The surfer wanders in and circles forever; all the importance in the web slowly drowns inside the clump.

Brin and Page's fix is almost silly: every so often, with probability 1−d, the surfer gets bored and teleports to a random page. That single move cures both diseases — she can always escape a trap or a dead end — and it quietly guarantees the whole thing has one and only one answer (a theorem named for Perron and Frobenius). The damping factor d is how link-loyal she stays; Brin and Page picked d = 0.85. Turn the knob and watch the cure work.

Importance is a property of the whole web

No page owns its rank. It's a standing wave across the entire link structure, and a single new link anywhere can re-sort everyone. Add and remove links below (click one node, then another, to toggle an arrow between them) and watch the crown move.

An old idea, renamed for the web

The notion that a thing's status is the eigenvector of a "who-esteems-whom" matrix is much older than Google. It was used to rank sociometric popularity in the 1950s (John Seeley, 1949; then Katz, 1953), formalised as eigenvector centrality by Phillip Bonacich in 1972, and — closest of all — applied to journals by Gabriel Pinski and Francis Narin in 1976, who reasoned that a citation from an influential journal should count for more, the exact recursion above. In 1998 Sergey Brin and Larry Page added the teleport term that tamed the real, messy web and called it PageRank — a pun on Larry Page's name. (Priority in this lineage is genuinely tangled and often disputed; the names above are the ones usually credited, not a settled verdict.) The same year, Jon Kleinberg's HITS split the idea into "hubs" and "authorities." Importance-as-a-fixed-point turned out to be one of those ideas the century kept re-discovering.