Real World: Google PageRank

Linear Algebra for Machine Learning · Axiom Academy

How Google uses eigenvectors to rank web pages In the 1990s, search engines ranked pages by keyword frequency. But pages could easily game this system by stuffing keywords. Google's founders, Larry Page and Sergey Brin, had a brilliant insight: This insight leads directly to an eigenvector problem! The Mathematics Behind PageRank Create a matrix M where M[i,j] = 1/k if page j links to k pages (including page i). This is a transition matrix representing random web surfing. Step 2: Define PageRank as an eigenvalue equation The PageRank vector r is the eigenvector with eigenvalue 1. It represents the steady-state probability distribution of randomly surfing the web! Step 3: Solve using power iteration Initialize a random distribution of page importance. Repeatedly apply the transition matrix. The result converges to PageRank. Interpreting M: Each column is a page. Each entry is the probability of moving to that row's page. Initial: r⁽⁰⁾ = (0.33, 0.33, 0.33) Iter 1: r⁽¹⁾ = M·r⁽⁰⁾ = (0.42, 0.17, 0.42) Iter 2: r⁽²⁾ = M·r⁽¹⁾ = (0.29, 0.42, 0.29) Iter 3: r⁽³⁾ = M·r⁽²⁾ = (0.35, 0.29, 0.35) Iter 10: r⁽¹⁰⁾ ≈ (0.40, 0.20, 0.40) ← Converged! Why This is an Eigenvector Problem This is the steady-state equation for a Markov chain. The solution is the eigenvector of M with eigenvalue 1. This eigenvector represents the stationary distribution—what happens in the long run. The actual Google algorithm includes:

This is the written version of the interactive lesson above. See the full Linear Algebra for Machine Learning course.