PageRank

in reviewThis lesson is complete and being validated before release - details may still change.

PageRank

Loading interactive demo…

A small web of pages, each circle sized by its rank, each arrow a link. Every page starts with the same rank. Each round a page hands its rank out equally along its links; a page with no links hands it to everyone. A page keeps a share d of what it is handed and adds the teleport share (1 - d) / n. The rounds repeat until a round moves the ranks less than the tolerance, or the cap is reached.Take the tour, or press and explore. Legend:

The panel beside the stage is the real PageRank class from the published library executing in your browser, with the current line highlighted.

Pages, drawn with a radius that grows with the square root of their rank, labelled with the rank.
The page whose rank is being computed, and the links handing rank to it.
The tapped page, whose rank the strip follows round by round.
Links; a page drawn as a dashed outline links nowhere.

iteration counts the rounds out of the cap, topnames the page with the largest rank and that rank, changeis how far the last round moved the ranks in total, sumthe ranks added up, always one. The bars show every page's rank; the strip shows the total change per round, or the tapped page's rank per round, with the finished run as a ghost.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

The random surfer. Imagine someone browsing at random: on each page they follow one of its links, chosen uniformly, with probability $d$ , and with probability $1 - d$ they jump to any page in the web, chosen uniformly. PageRank is the fraction of time the surfer spends on each page in the long run. Write $r_v$ for the rank of page $v$ , $\mathrm{out}(u)$ for the number of links leaving $u$ , and $n$ for the number of pages:

$r_v = \frac{1 - d}{n} + d \sum_{u \to v} \frac{r_u}{\mathrm{out}(u)}.$

The first term is the teleport share every page gets; the sum is what the pages linking to $v$ hand over, each splitting its rank equally among its links. The ranks sum to one, since every page hands out exactly what it holds.

Power iteration. Start every page at $1 / n$ and apply the update to all pages at once, repeatedly. Each round is one step of the surfer's walk; the ranks after $k$ rounds are the surfer's position after $k$ clicks, averaged over all the ways the walk could go. The stage plays one round per iterate event and stops when the total change $\sum_v |r_v' - r_v|$ falls under the tolerance.

Dangling pages. A page with no links strands the surfer. The update above would let its rank leak away, and the ranks would no longer sum to one. The fix is to treat a dangling page as linking to every page: its rank is spread uniformly before the links are summed, which is what the dangling event reports. On the chain this is what feeds rank back to the start.

Why the ranks settle, and to the same place. In matrix form the update is $r' = G r$ for a matrix $G$ whose columns are probability distributions with every entry at least $(1 - d) / n > 0$ . The Perron-Frobenius theorem says such a matrix has a unique probability vector that it leaves unchanged, and that repeated multiplication from any starting vector converges to it: PageRank is the eigenvector of $G$ for the eigenvalue 1, and the iteration is the standard way to find it. The error shrinks by a factor of at most $d$ per round, so about $\log(1/\varepsilon) / \log(1/d)$ rounds reach a tolerance $\varepsilon$ ; smaller $d$ settles faster but listens to the links less.

Loops and farms. The link farm shows the worst case for the rate: rank bounces between page 2 and its satellites, so the error alternates in sign and shrinks by almost exactly $d$ each round, and the default tolerance takes 41 rounds, beyond the slider. The hub has a ring among its spokes that mixes the walk and settles in 8. Damping is also what keeps a farm from swallowing everything: without it, a closed loop with an entry and no exit would collect all the rank.

Cost. Each round touches every page and every link: $O(V + E)$ , and $O(I(V + E))$ for $I$ rounds. On the web, $I$ is a few dozen and the matrix is never formed, only the adjacency lists.

Choices worth reading closely in the implementation (the code panel's comments and tracer checkboxes reveal the full published file):

Directed graphs only. An undirected graph would make every link mutual, so the constructor throws on one.
Weights are ignored. Every entry in a page's adjacency list is one link worth one share; a weighted link counts the same as any other, and the test pins it.
The dangling mass is spread before the links are summed, so incoming already holds mass / n when the first link adds its share, and the ranks sum to one after every round.
The whole row updates at once from the previous round's ranks, never page by page from half-updated values: the stage grows each circle as its rank event plays, but the arithmetic uses the old row throughout.
The change is the L1 norm of the difference between rounds, and the loop stops the first time it falls under the tolerance; the verdict says whether that happened or the cap arrived first.
Payloads round to four decimals so the narration reads cleanly; the returned ranks and history keep the raw values.

Two Stanford students, Larry Page and Sergey Brin, asked what the web's links said about its pages. A link as a citation, worth more from an important page, gives a circular definition that a simple iteration resolves: hand every page's rank out along its links and repeat until nothing moves. Their 1998 paper and 1999 report turned a classic of matrix theory, the resting distribution of a random walk, into the ranking that launched Google. The ideas were older: Leo Katz scored status in social networks the same way in 1953, and the theorem that promises a unique answer dates from 1907.

1907Oskar Perron - Proves that a square matrix with positive entries has a single largest eigenvalue with a positive eigenvector; Georg Frobenius extends it to irreducible non-negative matrices in 1912. Together they are why PageRank has exactly one answer.source
1953Leo Katz - Publishes 'A new status index derived from sociometric analysis' in Psychometrika: a person's status counts not only who chooses them but the status of the choosers, attenuated along each hop, the same circular idea applied to social networks.source
1998Sergey Brin and Larry Page - Present 'The anatomy of a large-scale hypertextual Web search engine' at the WWW7 conference in Brisbane, describing Google, a prototype search engine that ranks pages by the link structure of the web.source
1998Larry Page and Sergey Brin - Incorporate Google in September, in a garage in Menlo Park, with PageRank as the ranking at its core.source
1999Page, Brin, Motwani, and Winograd - Publish the Stanford InfoLab technical report 'The PageRank Citation Ranking: Bringing Order to the Web', which gives the method its name, the random surfer model, and the damping factor.source
2001Stanford University - Is granted US patent 6,285,999, 'Method for node ranking in a linked database', with Larry Page as inventor; Google holds an exclusive licence, and Stanford's shares in the company are later sold for hundreds of millions of dollars.source

Used today

Web search - The original use: a query-independent importance score for every page, combined with text relevance to order the results.
Citation analysis - Journals and papers ranked by who cites them, weighted by the rank of the citer: Eigenfactor and similar scores for scholarly impact.
Biology - Protein interaction networks and food webs ranked for the nodes whose removal matters most, and gene prioritisation by the same walk.
Sports and recommendation - Teams ranked by whom they beat and how strong those teams were; social networks suggest whom to follow with a personalised version of the same walk.

Did you know

The name is a pun: PageRank ranks pages, and it is named after Larry Page, its inventor. Google's own documentation has long credited the name to him.source
The patent belongs to Stanford, not Google. Stanford licensed it exclusively to Google in exchange for 1.8 million shares, which the university sold in 2005 for 336 million dollars.source
The random surfer is a real model: the damping factor of 0.85 is the chance the surfer follows a link rather than typing a fresh address, and the 1999 report chose it because it made the iteration settle in about fifty rounds on the whole web of the time.source
For years the Google Toolbar showed every page's PageRank as a green bar from 0 to 10, which made it the most watched number on the web for site owners, and bred the link farms it was eventually hidden to discourage.source

graph

damping0.85

iterations10

iteration: 8 of 10
top: n0 at 0.32
change: 0.0009
sum: 1.000

pagerank.ts

import type { Tracer } from "../trace";import type { AdjacencyGraph } from "./graph";export interface PageRankResult {  /** Each page's rank after the last iteration; the ranks sum to one. */  readonly ranks: readonly number[];  readonly rankOfPage: readonly number[];  /** How many iterations ran, converged or not. */  readonly iterations: number;  /** Whether the last iteration's L1 change fell under the tolerance. */  readonly converged: boolean;  /** The ranks before every iteration and after the last: `iterations + 1` rows, the first uniform. */  readonly history: readonly (readonly number[])[];  /** The pages with no outgoing link, whose rank is spread over every page each iteration. */  readonly dangling: readonly number[];}/** Payload ranks are shown to four decimals; the report keeps the raw values. */const round = (value: number): number => Math.round(value * 10_000) / 10_000;/** * PageRank by power iteration: every page starts with rank `1 / n`, and * each iteration a page hands its rank out equally along its links. A * page with no links (a dangling page) hands its rank to every page * equally instead, so no rank leaks out of the web. A damping factor `d` * keeps `d` of the handed-out rank and spreads the rest, `(1 - d) / n`, * over every page: the random surfer who follows a link with chance `d` * and jumps anywhere otherwise. The iteration stops when the L1 change * between two rounds falls under the tolerance, or after `maxIterations`. * * Only directed graphs: an undirected graph would make every page a * mutual link. Edge weights are ignored: every link counts once, each * entry in a page's adjacency list is one link. Ties and order are * deterministic; the ranks always sum to one. * * Time: O(I (V + E)). Space: O(I V) for the history. */export class PageRank {  constructor(    readonly graph: AdjacencyGraph,    readonly damping = 0.85,    readonly tolerance = 0.001,    private readonly tracer?: Tracer,  ) {    if (!graph.directed) throw new RangeError("PageRank needs a directed graph");    if (!(damping > 0 && damping < 1)) throw new RangeError(`damping ${damping} must lie strictly between 0 and 1`);    if (!(tolerance > 0)) throw new RangeError(`tolerance ${tolerance} must be positive`);  }  run(maxIterations = 30): PageRankResult {    if (!Number.isInteger(maxIterations) || maxIterations < 1) throw new RangeError(`maxIterations ${maxIterations} must be a positive integer`);    const n = this.graph.nodeCount;    const d = this.damping;    const outDegree = Array.from({ length: n }, (_, node) => this.graph.neighbors(node).length);    const dangling: number[] = [];    outDegree.forEach((degree, node) => {      if (degree === 0) dangling.push(node);    });    let ranks: number[] = Array.from({ length: n }, () => 1 / n);    let rankOfPage: number[] = Array.from({ length: n }, () => 1 / n);    const history: number[][] = [ranks.slice()];    const history: number[][] = [rankOfPage.slice()];    // ▸ every page starts equal: one nth of the rank each    this.tracer?.emit("init", { damping: d, ranks: ranks.map(round), tolerance: this.tolerance });    this.tracer?.emit("init", { damping: d, rankOfPage: rankOfPage.map(round), tolerance: this.tolerance });    let iterations = 0;    let converged = false;    for (let iteration = 1; iteration <= maxIterations; iteration++) {      iterations = iteration;      const mass = dangling.reduce((sum, node) => sum + ranks[node]!, 0);      const mass = dangling.reduce((sum, node) => sum + rankOfPage[node]!, 0);      // ▸ pages that link nowhere hand their rank to everyone      if (dangling.length > 0) this.tracer?.emit("dangling", { iteration, mass: round(mass), nodes: dangling.slice() });      // Every page receives the dangling mass evenly, then its share of each linking page's rank.      const incoming: number[] = Array.from({ length: n }, () => mass / n);      const handedIn: number[] = Array.from({ length: n }, () => mass / n);      for (let from = 0; from < n; from++) {        const degree = outDegree[from]!;        if (degree === 0) continue;        const share = ranks[from]! / degree;        const share = rankOfPage[from]! / degree;        for (const { to } of this.graph.neighbors(from)) incoming[to] = incoming[to]! + share;        for (const { to } of this.graph.neighbors(from)) handedIn[to] = handedIn[to]! + share;      }      const next: number[] = Array.from({ length: n }, () => 0);      let delta = 0;      let totalChange = 0;      for (let node = 0; node < n; node++) {        const value = (1 - d) / n + d * incoming[node]!;        const value = (1 - d) / n + d * handedIn[node]!;        next[node] = value;        delta += Math.abs(value - ranks[node]!);        totalChange += Math.abs(value - rankOfPage[node]!);        // ▸ a page's new rank: the teleport share plus d of what its links hand in        this.tracer?.emit("rank", { incoming: round(incoming[node]!), iteration, node, value: round(value) });        this.tracer?.emit("rank", { handedIn: round(handedIn[node]!), iteration, node, value: round(value) });      }      ranks = next;      rankOfPage = next;      history.push(ranks.slice());      history.push(rankOfPage.slice());      // ▸ one round done: how far did the ranks move in total?      this.tracer?.emit("iterate", { delta: round(delta), iteration, ranks: ranks.map(round) });      this.tracer?.emit("iterate", { totalChange: round(totalChange), iteration, rankOfPage: rankOfPage.map(round) });      if (delta < this.tolerance) {      if (totalChange < this.tolerance) {        converged = true;        break;      }    }    // ▸ settled under the tolerance, or stopped at the cap    this.tracer?.emit("verdict", { converged, iterations, ranks: ranks.map(round) });    this.tracer?.emit("verdict", { converged, iterations, rankOfPage: rankOfPage.map(round) });    return { ranks, iterations, converged, history, dangling };    return { rankOfPage, iterations, converged, history, dangling };  }}

top =: n0
rank =: 0.3192
change =: 0.0009
converged =: yes
iterations =: 8

n0 ranks highest at 0.3192; the last round moved the ranks 0.0009 in total, converged after 8 iterations.

import type { Tracer } from "../trace";import type { AdjacencyGraph } from "./graph";export interface PageRankResult { /** Each page's rank after the last iteration; the ranks sum to one. */ readonly ranks: readonly number[]; readonly rankOfPage: readonly number[]; /** How many iterations ran, converged or not. */ readonly iterations: number; /** Whether the last iteration's L1 change fell under the tolerance. */ readonly converged: boolean; /** The ranks before every iteration and after the last: `iterations + 1` rows, the first uniform. */ readonly history: readonly (readonly number[])[]; /** The pages with no outgoing link, whose rank is spread over every page each iteration. */ readonly dangling: readonly number[];}/** Payload ranks are shown to four decimals; the report keeps the raw values. */const round = (value: number): number => Math.round(value * 10_000) / 10_000;/** * PageRank by power iteration: every page starts with rank `1 / n`, and * each iteration a page hands its rank out equally along its links. A * page with no links (a dangling page) hands its rank to every page * equally instead, so no rank leaks out of the web. A damping factor `d` * keeps `d` of the handed-out rank and spreads the rest, `(1 - d) / n`, * over every page: the random surfer who follows a link with chance `d` * and jumps anywhere otherwise. The iteration stops when the L1 change * between two rounds falls under the tolerance, or after `maxIterations`. * * Only directed graphs: an undirected graph would make every page a * mutual link. Edge weights are ignored: every link counts once, each * entry in a page's adjacency list is one link. Ties and order are * deterministic; the ranks always sum to one. * * Time: O(I (V + E)). Space: O(I V) for the history. */export class PageRank { constructor( readonly graph: AdjacencyGraph, readonly damping = 0.85, readonly tolerance = 0.001, private readonly tracer?: Tracer, ) { if (!graph.directed) throw new RangeError("PageRank needs a directed graph"); if (!(damping > 0 && damping < 1)) throw new RangeError(`damping ${damping} must lie strictly between 0 and 1`); if (!(tolerance > 0)) throw new RangeError(`tolerance ${tolerance} must be positive`); } run(maxIterations = 30): PageRankResult { if (!Number.isInteger(maxIterations) || maxIterations < 1) throw new RangeError(`maxIterations ${maxIterations} must be a positive integer`); const n = this.graph.nodeCount; const d = this.damping; const outDegree = Array.from({ length: n }, (_, node) => this.graph.neighbors(node).length); const dangling: number[] = []; outDegree.forEach((degree, node) => { if (degree === 0) dangling.push(node); }); let ranks: number[] = Array.from({ length: n }, () => 1 / n); let rankOfPage: number[] = Array.from({ length: n }, () => 1 / n); const history: number[][] = [ranks.slice()]; const history: number[][] = [rankOfPage.slice()]; // ▸ every page starts equal: one nth of the rank each this.tracer?.emit("init", { damping: d, ranks: ranks.map(round), tolerance: this.tolerance }); this.tracer?.emit("init", { damping: d, rankOfPage: rankOfPage.map(round), tolerance: this.tolerance }); let iterations = 0; let converged = false; for (let iteration = 1; iteration <= maxIterations; iteration++) { iterations = iteration; const mass = dangling.reduce((sum, node) => sum + ranks[node]!, 0); const mass = dangling.reduce((sum, node) => sum + rankOfPage[node]!, 0); // ▸ pages that link nowhere hand their rank to everyone if (dangling.length > 0) this.tracer?.emit("dangling", { iteration, mass: round(mass), nodes: dangling.slice() }); // Every page receives the dangling mass evenly, then its share of each linking page's rank. const incoming: number[] = Array.from({ length: n }, () => mass / n); const handedIn: number[] = Array.from({ length: n }, () => mass / n); for (let from = 0; from < n; from++) { const degree = outDegree[from]!; if (degree === 0) continue; const share = ranks[from]! / degree; const share = rankOfPage[from]! / degree; for (const { to } of this.graph.neighbors(from)) incoming[to] = incoming[to]! + share; for (const { to } of this.graph.neighbors(from)) handedIn[to] = handedIn[to]! + share; } const next: number[] = Array.from({ length: n }, () => 0); let delta = 0; let totalChange = 0; for (let node = 0; node < n; node++) { const value = (1 - d) / n + d * incoming[node]!; const value = (1 - d) / n + d * handedIn[node]!; next[node] = value; delta += Math.abs(value - ranks[node]!); totalChange += Math.abs(value - rankOfPage[node]!); // ▸ a page's new rank: the teleport share plus d of what its links hand in this.tracer?.emit("rank", { incoming: round(incoming[node]!), iteration, node, value: round(value) }); this.tracer?.emit("rank", { handedIn: round(handedIn[node]!), iteration, node, value: round(value) }); } ranks = next; rankOfPage = next; history.push(ranks.slice()); history.push(rankOfPage.slice()); // ▸ one round done: how far did the ranks move in total? this.tracer?.emit("iterate", { delta: round(delta), iteration, ranks: ranks.map(round) }); this.tracer?.emit("iterate", { totalChange: round(totalChange), iteration, rankOfPage: rankOfPage.map(round) }); if (delta < this.tolerance) { if (totalChange < this.tolerance) { converged = true; break; } } // ▸ settled under the tolerance, or stopped at the cap this.tracer?.emit("verdict", { converged, iterations, ranks: ranks.map(round) }); this.tracer?.emit("verdict", { converged, iterations, rankOfPage: rankOfPage.map(round) }); return { ranks, iterations, converged, history, dangling }; return { rankOfPage, iterations, converged, history, dangling }; }}