Graphs, Ranking & Search

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?

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 d and 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.