PageRank

Random surfer

Prerequisites

graph TD
  Prob[Probability basics] --> Markov[Markov chains]
  Graph[Directed graphs] --> PR[PageRank]
  Markov --> PR
  MapReduce[MapReduce / batch jobs] --> PR

When to use

Global importance ranking over a large hyperlink or citation graph (web search, academic citations, recommendation graphs).
Steady-state visit probability when a random walk with teleportation models how traffic or attention flows.
Offline batch scoring where you can iterate until convergence (power method on sparse adjacency).

When not to use

You need fresh, personalized rankings per user or query — use learning-to-rank or embeddings, not static PageRank alone.
The graph is tiny — exact eigenvector solvers or direct linear algebra may be simpler than distributed iteration.
Manipulable link farms dominate without anti-spam — raw PageRank rewards artificial hubs unless you add trust and penalties.

Lab

On the interactive PageRank lab, pick a demo graph (classic web, hub-and-spoke, or spider trap), tune damping and power-iteration steps, and watch ranks on the link diagram and bar chart stabilize. Compare PageRank to the uniform (1/N) distribution, try Classic web or Spider trap presets, predict which node ranks highest after enough iterations, then reveal the top node and L1 distance from uniform.

Simple Fundamental Explanation

Imagine you arrive in a new city and want to find the best pizza place.

The old way (Keywords): You look in the phone book and find the restaurant that wrote the word “Pizza” the most times in their ad. (This is easily manipulated).
The PageRank way: You stand on a random street corner and start asking random people where they like to eat. Every time someone suggests a restaurant, you go there. Once there, you ask a random person in that restaurant where else they like to eat. You follow these recommendations endlessly.

After a year of doing this, you look at your notes. The restaurants you ended up standing inside the most often are the “most important” ones.

PageRank is the foundational algorithm that built Google. It treats the internet as a massive map. A link from Page A to Page B is a “vote”. But not all votes are equal. A vote from a highly trusted page (like Wikipedia) counts much more than a vote from a spam blog. PageRank uses a probabilistic “Random Surfer” model to mathematically calculate the inherent importance of every page on the internet.

Deep Dive: How It Works Under the Hood

PageRank models the internet as a directed graph. Nodes are web pages; edges are hyperlinks.

The Random Surfer Model

Imagine a person mindlessly clicking links on the internet.

They start on a random page.
They look at all the outgoing links on that page. They pick one completely at random and click it.
They repeat step 2 infinitely.

The PageRank of a webpage is defined as the steady-state probability that the random surfer will eventually end up on that specific page.

The Damping Factor (Teleportation)

What happens if the surfer gets stuck on a page with no outgoing links (a “dangling node”), or a small loop of pages that only link to each other (a “spider trap”)? They would be stuck forever, sucking up all the PageRank probability in the system.

To fix this, Google introduced the Damping Factor ( $d$ ). At every step, the surfer rolls a weighted die (usually $d = 0.85$ ).

85% of the time, they click a random link on the current page.
15% of the time, they get bored, type a completely random URL into their browser, and “teleport” to a random page anywhere on the internet.

This guarantees the math always converges to a stable probability distribution.

Visual Diagram

Web Graph:
(A) -----> (B)
 ^ \        |
 |  \       |
 |   v      v
 (D) <---- (C)

A links to B and C.
B links to C.
C links to D.
D links to A.

Because A has many incoming links (or links from important pages),
a random surfer will naturally spend more time on A than on B.
Probability of being on A > B > C > D.

Practical Example: Google Search Ranking

Before Google, search engines like AltaVista ranked pages based purely on text density. If you wanted to rank #1 for “Cars”, you just wrote “Cars” 10,000 times in hidden white text at the bottom of your page.

Larry Page and Sergey Brin realized that human behavior (creating hyperlinks) was a better signal of quality. If the New York Times linked to a car blog, that blog must be high quality.

By running the PageRank algorithm across the entire crawl of the internet, they assigned a global importance score to every page. When a user searched “Cars”, Google first found all pages containing the word “Cars”, and then sorted them by their global PageRank score. The result was a search engine so vastly superior to its competitors that it achieved near-monopoly status within a few years.

The Mathematics: Equations and In-Depth Analysis

1. The Core Equation

Let $P R (u)$ be the PageRank of page $u$ . Let $B_{u}$ be the set of pages that link to $u$ . Let $L (v)$ be the total number of outgoing links from page $v$ . Let $N$ be the total number of pages on the internet. Let $d$ be the damping factor.

The PageRank of page $u$ is calculated iteratively:

P R (u) = \frac{1 - d}{N} + d v \in B_{u} \sum \frac{P R ( v )}{L ( v )}

Explanation of the terms:

$\frac{1 - d}{N}$ : The probability that the surfer teleported directly to page $u$ out of boredom.
$\frac{P R ( v )}{L ( v )}$ : The probability the surfer was on page $v$ , and happened to click the specific link leading to $u$ .
The summation adds up this probability for every single page that links to $u$ .

2. The Markov Chain and Eigenvectors

Mathematically, the Random Surfer model is a Markov Chain. The internet is represented as an $N \times N$ transition probability matrix $M$ , where $M_{ij}$ is the probability of moving from page $j$ to page $i$ .

The PageRank vector $R$ (containing the scores for all $N$ pages) is the solution to the equation:

R = (\frac{1 - d}{N} E + d M) R

(where $E$ is a matrix of all ones).

Because this forms a stochastic matrix, by the Perron-Frobenius theorem, the PageRank vector $R$ is exactly the principal eigenvector of the modified matrix, corresponding to the eigenvalue 1.

Google solves this not by calculating eigenvectors directly (which is impossible for a trillion-by-trillion matrix), but by using the Power Iteration method. They initialize all pages with $P R = 1/ N$ , and then repeatedly multiply the vector by the matrix using MapReduce until the values stop changing (convergence).

Lab

Power iteration on a tiny directed graph: each step applies the random-surfer update with damping d and teleport to all nodes on dangling pages — same recurrence as the README equation.

Damping (d)85% teleport 15%

Power iterations8 steps (suggested ~15)

Solid bars: PageRank after 8 steps. Faded bars: uniform 1/N. Accent node is current top rank; thicker edges connect higher-ranked nodes.

On Classic web with d = 85%, after 8 power steps, has the distribution converged (last-step L1 change < 0.05)?

Classic web: 8 iterations, top C (40.6%). Last step Δ = 0.0059.