PageRank

A Bit of History

Larry Page and Sergey Brin described PageRank while developing an early large-scale web search system at Stanford in the late 1990s. The central idea borrowed the spirit of academic citation: a link is a vote, but a vote from an important page should count more than one from an obscure page.

The clever step is recursive. Importance flows through a directed graph until the scores become self-consistent. That connects PageRank to Markov chains, stationary distributions, eigenvectors, and iterative numerical methods—not merely to counting incoming links.

The Random-Surfer Mental Model

Imagine a visitor who browses forever. From the current page, the visitor:

• with probability $d$, follows one outgoing link chosen uniformly;
• with probability $1-d$, teleports to a page selected from a fixed probability distribution.

PageRank is the long-run probability of finding this visitor on each page. Uniform teleportation chooses every page with probability $1/N$. Personalized PageRank replaces that uniform choice with a preference vector, biasing the walk toward a topic, user, or seed set.

The PageRank Equation

With uniform teleportation and no dangling pages, the score of page $v$ satisfies

$$r(v)=\frac{1-d}{N}+d\sum_{u\to v}\frac{r(u)}{L(u)},$$

where $L(u)$ is the number of outgoing links from $u$. The formula has two clearly different sources of probability:

1. Teleportation: every page receives a base amount $(1-d)/N$.
2. Link flow: every non-dangling page distributes $d\,r(u)$ equally among its outgoing neighbors.
3. Dangling redistribution: rank held by pages with no outgoing links is distributed according to the teleportation vector.
4. Repeat synchronously: compute an entirely new vector from the old one until the total change is below a tolerance.

Dangling Pages, Rank Sinks, and Teleportation

A dangling page has no outgoing links. If its rank is simply discarded, total probability shrinks every iteration—the flaw in many short PageRank examples. Treat a dangling page as linking according to the teleportation distribution. With uniform teleportation, its rank is spread evenly across all pages.

A rank sink is a closed region with no links leading out. Pure link-following can trap all probability there. Separate directed cycles can also make a walk periodic. Teleportation fixes both problems by making the transition matrix positive when the preference vector is positive.

For a general preference vector $p$ with $\sum_v p(v)=1$, the complete update is

$$r_{k+1}(v)=(1-d)p(v)+d\left[D_k p(v)+\sum_{u\to v}\frac{r_k(u)}{L(u)}\right],$$

where $D_k=\sum_{u:L(u)=0}r_k(u)$ is the dangling mass at iteration $k$.

Visual Walkthrough

Let $A$ link to $B$ and $C$, $B$ link only to $C$, and $C$ link only to $A$. Start with $r_0=(1/3,1/3,1/3)$, use $d=0.85$, and teleport uniformly. The base contribution is $(1-d)/3=0.05$ per page.

The Same Idea as a Matrix Equation

Construct a column-stochastic link matrix $S$: column $u$ divides one unit equally among $u$'s outgoing neighbors; a dangling column is replaced by the preference vector $p$. The Google matrix is

$$G=dS+(1-d)p\mathbf{1}^{\mathsf T},$$

and PageRank is the stationary vector satisfying $r=Gr$. Because columns sum to one, multiplying by $G$ preserves total probability. Power iteration simply computes $r_{k+1}=Gr_k$ until the vector stops changing.

Why Power Iteration Converges

With $0\le d<1$ and a strictly positive preference vector, every entry of $G$ is positive. The resulting Markov chain is irreducible and aperiodic, so it has one positive stationary distribution.

There is also a direct numerical intuition. The stochastic link step cannot increase $L_1$ distance, and teleportation contributes the same fixed vector to every update. Therefore the PageRank update $F$ satisfies

$$\lVert F(x)-F(y)\rVert_1\le d\,\lVert x-y\rVert_1.$$

Since $d<1$, each iteration contracts differences by at least a factor of $d$. Banach's fixed-point theorem gives a unique fixed point and convergence from any starting probability vector. Smaller $d$ contracts faster; larger $d$ lets link structure dominate more strongly.

Complexity Analysis

With adjacency lists, one synchronous iteration initializes $V$ new scores and traverses every edge once:

$$\text{Time per iteration: }O(V+E) \qquad \text{Space: }O(V+E).$$

After $k$ iterations, total time is $O(k(V+E))$. The contraction bound implies roughly $k=O(\log(1/\varepsilon)/(1-d))$ iterations to reduce error to scale $\varepsilon$, though actual convergence depends on the graph, norm, starting vector, and stopping rule. Sparse linear algebra and vertex-centric message passing make the update naturally distributable.

Implementation

These versions use synchronous updates, redistribute dangling mass, stop on $L_1$ change rather than a fixed iteration count, validate link targets, and leave the input graph unchanged. The Python version also supports a personalized teleportation vector.

def pagerank(
    outlinks, damping=0.85, tolerance=1e-12,
    max_iterations=1000, personalization=None,
):
    """Return (scores, iterations_used, final_L1_change)."""
    n = len(outlinks)
    if n == 0:
        raise ValueError("graph must contain at least one page")
    if not 0 <= damping < 1:
        raise ValueError("damping must satisfy 0 <= d < 1")
    if tolerance <= 0 or max_iterations < 1:
        raise ValueError("invalid stopping parameters")

    links = []
    for row in outlinks:
        unique = list(dict.fromkeys(row))  # treat repeated URLs as one link
        if any(v < 0 or v >= n for v in unique):
            raise ValueError("outlink target outside 0..n-1")
        links.append(unique)

    if personalization is None:
        preference = [1.0 / n] * n
    else:
        if len(personalization) != n or any(x < 0 for x in personalization):
            raise ValueError("invalid personalization vector")
        total = sum(personalization)
        if total == 0:
            raise ValueError("personalization must have positive mass")
        preference = [x / total for x in personalization]

    rank = preference.copy()
    delta = float("inf")

    for iteration in range(1, max_iterations + 1):
        dangling_mass = sum(rank[u] for u in range(n) if not links[u])
        new_rank = [
            ((1 - damping) + damping * dangling_mass) * preference[v]
            for v in range(n)
        ]

        for u in range(n):
            if links[u]:
                share = damping * rank[u] / len(links[u])
                for v in links[u]:
                    new_rank[v] += share

        delta = sum(abs(new_rank[v] - rank[v]) for v in range(n))
        rank = new_rank
        if delta <= tolerance:
            break

    return rank, iteration, delta


# A -> B, C ; B -> C ; C -> A
scores, iterations, delta = pagerank([[1, 2], [2], [0]])
print([round(x, 6) for x in scores])  # [0.38779, 0.214811, 0.3974]
print(sum(scores))                    # approximately 1.0

#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <stdexcept>
#include <utility>
#include <vector>

struct PageRankResult {
    std::vector<double> scores;
    int iterations;
    double delta;
};

PageRankResult pagerank(std::vector<std::vector<int>> links,
                        double damping = 0.85,
                        double tolerance = 1e-12,
                        int maxIterations = 1000) {
    const int n = static_cast<int>(links.size());
    if (n == 0 || damping < 0 || damping >= 1 ||
            tolerance <= 0 || maxIterations < 1)
        throw std::invalid_argument("invalid PageRank parameters");

    for (auto& row : links) {
        for (int v : row)
            if (v < 0 || v >= n) throw std::invalid_argument("invalid target");
        std::sort(row.begin(), row.end());
        row.erase(std::unique(row.begin(), row.end()), row.end());
    }

    std::vector<double> rank(n, 1.0 / n);
    double delta = 0.0;
    for (int iteration = 1; iteration <= maxIterations; ++iteration) {
        double danglingMass = 0.0;
        for (int u = 0; u < n; ++u)
            if (links[u].empty()) danglingMass += rank[u];

        const double base = ((1.0 - damping) + damping * danglingMass) / n;
        std::vector<double> next(n, base);
        for (int u = 0; u < n; ++u) {
            if (!links[u].empty()) {
                const double share = damping * rank[u] / links[u].size();
                for (int v : links[u]) next[v] += share;
            }
        }

        delta = 0.0;
        for (int v = 0; v < n; ++v) delta += std::abs(next[v] - rank[v]);
        rank = std::move(next);
        if (delta <= tolerance) return {rank, iteration, delta};
    }
    return {rank, maxIterations, delta};
}

int main() {
    PageRankResult result = pagerank({{1, 2}, {2}, {0}});
    std::cout << std::fixed << std::setprecision(6);
    for (double score : result.scores) std::cout << score << ' ';
    std::cout << '\n'; // 0.387790 0.214811 0.397400
}

import java.util.*;

public class PageRank {
    static final class Result {
        final double[] scores;
        final int iterations;
        final double delta;
        Result(double[] scores, int iterations, double delta) {
            this.scores = scores;
            this.iterations = iterations;
            this.delta = delta;
        }
    }

    static Result compute(List<List<Integer>> outlinks,
                          double damping, double tolerance, int maxIterations) {
        int n = outlinks.size();
        if (n == 0 || damping < 0 || damping >= 1 ||
                tolerance <= 0 || maxIterations < 1)
            throw new IllegalArgumentException("invalid PageRank parameters");

        List<List<Integer>> links = new ArrayList<>();
        for (List<Integer> row : outlinks) {
            LinkedHashSet<Integer> unique = new LinkedHashSet<>();
            for (int v : row) {
                if (v < 0 || v >= n) throw new IllegalArgumentException("invalid target");
                unique.add(v);
            }
            links.add(new ArrayList<>(unique));
        }

        double[] rank = new double[n];
        Arrays.fill(rank, 1.0 / n);
        double delta = 0.0;

        for (int iteration = 1; iteration <= maxIterations; iteration++) {
            double danglingMass = 0.0;
            for (int u = 0; u < n; u++)
                if (links.get(u).isEmpty()) danglingMass += rank[u];

            double base = ((1.0 - damping) + damping * danglingMass) / n;
            double[] next = new double[n];
            Arrays.fill(next, base);
            for (int u = 0; u < n; u++) {
                if (!links.get(u).isEmpty()) {
                    double share = damping * rank[u] / links.get(u).size();
                    for (int v : links.get(u)) next[v] += share;
                }
            }

            delta = 0.0;
            for (int v = 0; v < n; v++) delta += Math.abs(next[v] - rank[v]);
            rank = next;
            if (delta <= tolerance) return new Result(rank, iteration, delta);
        }
        return new Result(rank, maxIterations, delta);
    }

    public static void main(String[] args) {
        List<List<Integer>> outlinks = List.of(
            List.of(1, 2), List.of(2), List.of(0)
        );
        Result result = compute(outlinks, 0.85, 1e-12, 1000);
        System.out.println(Arrays.toString(result.scores));
    }
}

Choosing the Damping Factor

The familiar value $0.85$ is a convention, not a mathematical constant. Choose $d$ according to the meaning of a “restart,” the desired locality of a personalized ranking, and the convergence budget. Report it with results because changing $d$ changes the question being answered.

Where PageRank-Style Scores Help

Limitations and Common Pitfalls

Exercises