Too many answers
Type two words into a search engine and it may find millions of pages that contain them. Finding them is the easy part. Long before you searched, programs called crawlers followed links from page to page, copying what they found, and the engine built an index: for every word, a list of the pages that use it, like the index at the back of a book. Looking your words up in that index takes a fraction of a second.
The hard part is the order. Nobody reads past the first few results, so the engine has to guess, out of millions of matches, which handful you actually want. Counting how often your words appear is easy to game: a page can repeat them a thousand times. The words on a page are chosen by whoever wrote it. Early search engines needed something that the page’s own author could not simply write in.
Links as votes
In 1998 Larry Page and Sergey Brin, then graduate students, built a search engine around an idea borrowed from science: a paper that many other papers cite is probably important. On the web, the citations are links. When someone puts a link on their page, they are pointing readers somewhere they think is worth a visit. Count the links into a page and you have a rough vote on how useful other people find it.
But a plain count is easy to game too: anyone can make a hundred empty pages that all link to theirs. So Page and Brin weighted the votes. A link from a page that is itself important counts for more. And a page that links to many others splits its vote between them, so each of those links counts for less. They called the result PageRank.
Try it: choose Three quiet pages under Pages linking to yours, then Plus the hub. Three links from pages hardly anyone links to add about three points to your page’s rank; one link from the hub, which most pages link to, adds nearly seven more.
The random surfer
That definition sounds circular, since a page’s rank depends on the ranks of the pages that link to it, which depend on others in turn. There is a way to picture it that settles the circle.
Imagine a random surfer who starts on any page and clicks one of its links, chosen at random. On the new page, they click another random link, and so on, for ever. Pages with many links in get visited often. Pages linked from often-visited pages get visited often too, because the surfer keeps arriving at those pages and leaving through their links. A page that splits its visitors among many links sends fewer down each one.
Over a long walk, the share of the surfer’s time spent on each page settles down to a fixed number. That number is the page’s PageRank. In the scene the ranks always add up to 100%, because the surfer is always somewhere.
Try it: drag Let the surfer walk from Ranks towards Random surfer. After ten clicks the orange bars are mostly luck. After a thousand, each bar is close to its page’s plinth, and the readout shows the largest gap shrinking.
Why the surfer sometimes jumps
A surfer who only ever clicks links can get stuck: in a corner of the web that links only to itself, they would go round it for ever, and all the rank would drain into that corner. Real people also give up and type a new address. So the surfer is given a second rule. At each step they click a link with some chance, usually set to 85%, and otherwise jump to any page at random. That chance is called the damping factor.
The jumps give every page a small floor of visits, so no page’s rank is ever zero. Lower the chance of clicking and the jumps take over: at 0% the surfer ignores links completely and every page gets the same rank. Raise it and the links decide almost everything, so rank pools in the pages that the most links lead to.
Try it: slide Chance of clicking a link from 0% to 95% and watch the plinths spread apart, from eight equal heights to a tall hub and pages barely off the table.
Working it out
Nobody computes PageRank by simulating one surfer: it would take far too many clicks to settle for billions of pages. Instead, the engine pictures a whole crowd of surfers spread evenly over the pages, and moves them all one step at once. Each page sends its share of the crowd out along its links, split evenly between them, and a share of every page’s crowd jumps at random. After the step, each page counts who arrived. Repeat, and after a few dozen rounds the counts stop changing. Written as a rule for one page :
Here is the number of pages, is the damping factor, and the sum runs over every page that links to , each passing on its own rank divided by , its number of links out. The thickness of each link in the scene is that share, .
Gaming the ranks
As soon as rank was worth money, people tried to fake it. Link farms are networks of pages built only to link to one another and to a page someone wants to promote. Weighting by rank blunts this, because pages nobody else links to have little rank to give. Bought links, spam comments and hidden links led search engines to add rules of their own: a link can be marked as one the site does not vouch for, and pages caught in schemes are pushed down.
What this model leaves out
The scene has eight pages; the web has billions, and an engine like Google’s weighs PageRank alongside hundreds of other signals, from the words on a page and how recently it changed to where you are and what you searched for before. How much any one of them counts is not published.
Every page here links to at least one other. A real page with no links out would trap the surfer; the usual fix is to have them jump to a random page from there. The scene also treats every link on a page as equally likely to be clicked, while later versions of the idea weight links by where they sit and how likely people are to follow them. The surfer’s walk is one fixed run of random choices, so the bars always end up in the same place for the same settings; a different run would wander differently on the way and settle on the same ranks.