PageRank

In the late 1990s the web was a mess of pages and nobody could find anything. Early search engines ranked results by counting keywords, which was trivial to game: stuff a page with "best cheap flights" a hundred times and you floated to the top.

Two Stanford students, Larry Page and Sergey Brin, asked a different question. Forget what a page says about itself — look at who links to it. A link is a vote, and a vote from an already-important page should count for more. But importance is circular: a page is important if important pages link to it, which depends on their importance, and so on.

The clever escape from that circle is to imagine a random surfer who clicks links forever. The fraction of time the surfer spends on each page is its PageRank. Pages that catch the surfer often are important — no keyword stuffing required.

Here is a tiny web of five pages and the links between them. Each page starts with the same importance. Press Step to push importance along the links once: every page hands its current score to the pages it links to, split evenly. Keep stepping and watch the numbers stop moving.

<p class="hint">{{hint}}</p>
<div id="pages" class="pages"></div>
<div class="status" id="status">{{step_zero}}</div>
<div class="btns">
  <button id="step" type="button">{{btn_step}}</button>
  <button id="run" type="button">{{btn_run}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.pages { display: flex; flex-direction: column; gap: .5rem; margin: .4rem 0 .2rem; }
.row { display: flex; align-items: center; gap: .6rem; }
.label { width: 92px; font: 600 13px ui-monospace, monospace; color: #1d3557; }
.label small { display: block; font: 400 11px system-ui; color: #6b7785; }
.track { flex: 1; height: 22px; background: #eef2f6; border-radius: 6px; overflow: hidden; }
.bar { height: 100%; width: 0; background: #2a6f97; border-radius: 6px;
       transition: width .35s ease; }
.bar.lead { background: #1d3557; }
.pct { width: 54px; text-align: right; font: 700 13px ui-monospace, monospace; color: #1d3557; }
.status { font-size: .95rem; font-weight: 600; margin: .7rem 0 .5rem; min-height: 1.3em; color: #2a6f97; }
.status.done { color: #0a7d33; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }

// Code not found

This is power iteration. Notice two things. First, the ranking converges — after a handful of steps the scores barely change, no matter where you started. Second, that stable distribution is exactly the dominant eigenvector of the link matrix: the one vector the system keeps returning to. Checking a proposed ranking is one matrix multiply; finding it is just repeating that multiply until it stops moving.

What exactly are we computing? Build the link matrix M: column j tells you how page j splits its importance among the pages it links to. The random surfer's long-run behaviour is the vector r that doesn't change when you apply M — that is, M·r = r. In linear algebra that r is the dominant eigenvector (eigenvalue 1) of M; in probability it's the stationary distribution of a Markov chain.

• It exists and is unique. The Perron–Frobenius theorem guarantees that a column-stochastic matrix with a small "teleport" probability — the surfer occasionally jumps to a random page — has exactly one stationary vector with all-positive entries. Page and Brin used a damping factor (about 0.85) to enforce exactly this.
• It's in P. You never form or invert a giant matrix. Power iteration — multiply, normalize, repeat — converges geometrically; the number of steps depends on the gap to the second eigenvalue, not on the size of the web. Each step is linear in the number of links.
• So this is the easy side of complexity. Unlike the NP-hard graph problems on this site, ranking the entire web is a polynomial-time linear-algebra computation. The genius wasn't beating intractability — it was spotting that "importance" was secretly an eigenvector.

That's the contrast worth keeping: a Traveling Salesman tour explodes combinatorially, but the surfer's resting place is found by patient, predictable multiplication.

"Importance flows along a network" describes far more than the web, so the eigenvector trick shows up everywhere:

• Web search: PageRank launched Google and remains one signal among many for ordering results.
• Recommendations: random-walk scores over "who watched what" or "who follows whom" power video, music and friend suggestions.
• Science and bibliometrics: ranking journals and researchers by citation flow is PageRank on the citation graph (the "Eigenfactor" metric).
• Biology and chemistry: variants find the most central proteins in interaction networks or the key reactions in a metabolic pathway.
• Fraud and trust: ranking accounts by who links to or transacts with them helps surface spam, bots and money laundering.

Understand PageRank and you understand eigenvector centrality — a measure of who matters that underlies recommendations, graph analysis and network science across fields.

PageRank is a rare kind of breakthrough: not a new algorithm wrestling with an impossible problem, but a new way of seeing an old one. "Which page is important?" looked hopelessly circular until Page and Brin recast it as "where does a random surfer rest?" — and that resting place is just the dominant eigenvector of the link matrix, found by repeated multiplication.

It sits firmly on the easy side of the complexity map: polynomial time, guaranteed to exist, guaranteed to converge. The lesson isn't that hard problems became easy — it's that the right question can turn a tangle into a single, computable number. For the problems where no such trick exists, see P vs NP.