The Random Surfer
A surfer clicks random links around a tiny web. The pages she lands on most often are the ones the web "votes" as important.
Press Surf and watch the surfer hop from page to page. Can you spot which page she keeps coming back to?
A tiny web
Edit the web: tap a page, then tap another page to add (or remove) a link from the first to the second. Node size is its PageRank.
Challenges
Let her surf: reach 1000 steps with the surfer within 6% of the true PageRank.
Do the maths: press "Run until settled" and watch the orange bars stop moving.
Make her restless: slide the click chance to 0.55 or below and watch the pages even out.
Boost your page: use links alone to make the Bike Shop the number one page.
Try the cheat: add the link farm and watch the Bike Shop's PageRank jump by a quarter or more.
What just happened?
- The surfer follows a random link, but now and then gets bored and jumps to any page. Pages with many good pages linking to them are visited more.
- The visit counts settle towards a fixed set of shares. Those shares are the PageRank of each page.
- The orange bars get the same answer without any surfer: each page repeatedly shares its score among its links until nothing changes.
- Adding links to a page raised its score. A link from an important page is worth more than one from a nobody.
- A link farm helps for a while, which is why real search engines work hard to spot and ignore these tricks.
For grown-ups: what's really going on
PageRank (Brin and Page, 1998) is the stationary distribution of a Markov chain on the link graph. With damping factor d and N pages: PR(j) = (1 − d)/N + d · Σi→j PR(i) / outdeg(i).
- The random surfer follows a uniformly random out-link with probability
dand teleports to a uniformly random page otherwise. Teleporting makes the chain ergodic, so a unique answer exists. - Power iteration multiplies the current score vector by the transition matrix repeatedly. It converges geometrically at a rate of about
d, which is why smaller damping settles faster. Pages with no out-links (dangling nodes) spread their score evenly over all pages. - The surfer's visit frequencies converge to the same vector by the ergodic theorem, with error shrinking like
1/√steps. This is a Monte Carlo estimate of the exact answer. - A link farm manufactures in-links. Real engines combine PageRank with hundreds of other signals, TrustRank-style seeds of trusted pages, and spam detection, so this simple version is easy to game and real ones are not.
- The same idea ranks nodes in any graph: papers, accounts, roads, even proteins.
Further reading: Brin and Page, The anatomy of a large-scale hypertextual web search engine · Langville and Meyer, Google's PageRank and Beyond.