How Google’s PageRank Revolutionized Web Search: The Math Behind the Algorithm

Introduction

Google, founded in 1998, quickly became the dominant search engine, largely thanks to a mathematical breakthrough behind its ranking system.

Traditional search relies on small, well‑sorted, low‑duplicate data sets, but the Web violates these conditions: it contains billions of pages, lacks consistent classification, and yields massive duplicate results.

Basic Idea

In 1996, Stanford graduate students Larry Page and Sergey Brin sought a better ranking method. Inspired by academic citation counts, they proposed using the web’s link structure: a page linked by many others, especially high‑ranked ones, should rank higher.

This leads to a recursive definition: the rank of a page depends on the ranks of pages linking to it. Modeling a “random surfer” who follows links uniformly, the probability vector p_n evolves as p_{n+1}=H p_n, where H_{ij}= (link from j to i)/N_j.

In matrix form: p_{n+1}=H p_n. This is a Markov process, but H may have columns of zeros (dangling pages), preventing convergence.

Problems and Solutions

Three issues arise: existence of the limit lim_{n→∞} p_n, independence from the initial distribution p_0, and meaningfulness of the limit for ranking. The original formulation fails all three.

To fix dangling pages, Page and Brin replace zero columns with a uniform vector e/N, yielding matrix S = H + e a^T / N, which is stochastic.

To ensure convergence, they introduce a damping factor α (typically 0.85) and allow the surfer to jump to any page with probability 1‑α. The resulting Google matrix is G = α S + (1‑α) e e^T / N, which is a primitive (positive) stochastic matrix.

Iterating p_{n+1}=G p_n converges to a unique stationary distribution p, whose entries give the PageRank scores.

Conclusion

PageRank provided a mathematically sound, link‑based ranking that was hard to manipulate and independent of query terms, enabling fast, reliable search. Although Google’s current ranking incorporates many additional signals, PageRank remains a foundational concept, influencing citation metrics and other ranking systems.

Source: 卢昌海, http://www.changhai.org/articles/technology/misc/google_math.php