PageRank

A Bit of History

Larry Page and Sergey Brin, then Stanford PhD students, described PageRank in a 1998 technical report, "The PageRank Citation Ranking: Bringing Order to the Web," and the same year in "The Anatomy of a Large-Scale Hypertextual Web Search Engine" — the paper that effectively described the founding architecture of Google. The algorithm's core mathematical idea — ranking importance via a graph's dominant eigenvector — connects directly back to the spectral graph theory of Part 20, applied here to a directed "who links to whom" web graph rather than an undirected graph.

Working Principle: The Random Surfer

Model a hypothetical "random surfer" browsing the web: at each step, with probability \(d\) (the damping factor, typically 0.85), they click a uniformly random outgoing link on the current page; with probability \(1-d\), they instead "teleport" to a uniformly random page anywhere on the web (modeling someone typing a fresh URL rather than following a link). A page's PageRank is defined as the long-run fraction of time this random surfer spends on that page:

$$PR(p) = \frac{1-d}{N} + d \sum_{q \to p} \frac{PR(q)}{L(q)}$$

where \(N\) is the total number of pages, the sum runs over every page \(q\) linking to \(p\), and \(L(q)\) is the number of outgoing links on page \(q\) (so each page distributes its rank equally among its own outgoing links).

Worked Example

Consider 3 pages: A links to B and C; B links only to C; C links only to A. Initializing all three pages with equal rank \(1/3\), one iteration redistributes rank according to the linking structure: C receives contributions from both A (split between B and C) and B (all going to C), quickly accumulating the highest rank, since it is the most "linked-to" page overall — reflecting the intuitive idea that pages many other pages point to should rank higher, exactly like citation counts in academic papers, which directly inspired the algorithm's name and original framing.

Why Power Iteration Converges

Computing PageRank via power iteration — repeatedly applying the update equation to an initial guess vector, normalizing, and repeating — is guaranteed to converge to the true dominant eigenvector because the damping factor \(d < 1\) guarantees the transition matrix is irreducible and aperiodic (the "teleportation" possibility ensures every page can, in principle, reach every other page), which by the Perron-Frobenius theorem guarantees a unique dominant eigenvalue of exactly 1, with an all-positive eigenvector that power iteration is mathematically guaranteed to converge toward regardless of the starting guess.

Complexity Analysis

Each power iteration step touches every edge once, and convergence typically requires \(O(\log N)\) iterations in practice for web-scale graphs (formally bounded by the "spectral gap" between the top two eigenvalues):

$$\text{Time per iteration: } O(E) \qquad \text{Total: } O(E \log N) \text{ (typical practical convergence)}$$

This linear-per-iteration cost is precisely why PageRank scales to web-sized graphs with billions of pages — and precisely why it is a natural candidate for the distributed Pregel-style "think like a vertex" processing model from Part 23, since each iteration only requires each page to exchange rank estimates with its direct neighbors.

Implementation

def pagerank(n, outlinks, damping=0.85, iterations=100):
    """
    n: number of pages (0-indexed). outlinks: outlinks[i] = list of pages i links to.
    Returns the PageRank vector after power iteration.
    """
    rank = [1.0 / n] * n
    out_degree = [len(outlinks[i]) for i in range(n)]

    for _ in range(iterations):
        new_rank = [(1 - damping) / n] * n
        for i in range(n):
            if out_degree[i] == 0:
                continue  # dangling page: contributes nothing here (simplified)
            share = damping * rank[i] / out_degree[i]
            for j in outlinks[i]:
                new_rank[j] += share
        rank = new_rank

    return rank

# A -> B, C ; B -> C ; C -> A
outlinks = [[1, 2], [2], [0]]
print(pagerank(3, outlinks))  # C ends up with the highest rank

#include <vector>
#include <iostream>
using namespace std;

vector<double> pagerank(int n, vector<vector<int>>& outlinks, double damping = 0.85, int iterations = 100) {
    vector<double> rank(n, 1.0 / n);
    vector<int> outDegree(n);
    for (int i = 0; i < n; i++) outDegree[i] = outlinks[i].size();

    for (int iter = 0; iter < iterations; iter++) {
        vector<double> newRank(n, (1 - damping) / n);
        for (int i = 0; i < n; i++) {
            if (outDegree[i] == 0) continue;
            double share = damping * rank[i] / outDegree[i];
            for (int j : outlinks[i]) newRank[j] += share;
        }
        rank = newRank;
    }
    return rank;
}

int main() {
    vector<vector<int>> outlinks = {{1, 2}, {2}, {0}};
    vector<double> rank = pagerank(3, outlinks);
    for (double r : rank) cout << r << " ";
    cout << endl;
    return 0;
}

import java.util.*;

class PageRank {
    static double[] compute(int n, List<List<Integer>> outlinks, double damping, int iterations) {
        double[] rank = new double[n];
        Arrays.fill(rank, 1.0 / n);
        int[] outDegree = new int[n];
        for (int i = 0; i < n; i++) outDegree[i] = outlinks.get(i).size();

        for (int iter = 0; iter < iterations; iter++) {
            double[] newRank = new double[n];
            Arrays.fill(newRank, (1 - damping) / n);
            for (int i = 0; i < n; i++) {
                if (outDegree[i] == 0) continue;
                double share = damping * rank[i] / outDegree[i];
                for (int j : outlinks.get(i)) newRank[j] += share;
            }
            rank = newRank;
        }
        return rank;
    }

    public static void main(String[] args) {
        List<List<Integer>> outlinks = Arrays.asList(
            Arrays.asList(1, 2), Arrays.asList(2), Arrays.asList(0)
        );
        double[] rank = compute(3, outlinks, 0.85, 100);
        System.out.println(Arrays.toString(rank));
    }
}

Real-World Applications

Exercises

1. Trace through 2-3 power iterations by hand on the 3-page worked example, confirming that page C's rank grows fastest across iterations.
2. Explain, in your own words, why the damping factor \(d < 1\) (teleportation) is necessary for the algorithm to converge, connecting this to the Perron-Frobenius theorem's irreducibility requirement.
3. Modify the implementation to correctly redistribute a "dangling page" (a page with zero outgoing links) rank uniformly across all pages, rather than silently discarding it as the simplified version above does.
4. Challenge: Research how PageRank connects to Markov chain stationary distributions, and explain why the random-surfer model is equivalent to finding a Markov chain's steady-state probabilities.

Limitations