PageRank Simulation

What the simulation shows

A link is a vote, but votes are weighted: a link from a page that many others point to is worth more, and a page with many out-links splits its vote among them. PageRank makes that recursive definition precise, and the three graphs in the lab each show one of its consequences.

• Toy web: who links to you matters more than how many. Page C collects links from five pages and ranks first. Its only out-link goes to A, so A, with a single in-link, ranks second, above D, which has two.
• Dangling page. Page F has no out-links, like a PDF or an image. A surfer who reaches it has nowhere to click, so this model sends it to a page chosen uniformly at random; its rank is spread over every page.
• Two clusters, one-way bridge. Only D links from the left cluster to the right one, and nothing links back. Random jumps are the only way out of the right cluster, so it accumulates rank: about two-thirds of the total at d = 0.85 and about 95% at d = 0.99.

Press Play to watch the surfer: it starts slowly enough to follow single hops, then speeds up while its visit shares (orange bars) settle onto the power-iteration values (blue).

The equations and the power method

With n pages, damping factor d and out-degree k_i for page i, the PageRank vector r satisfies

In matrix form r = Gr, where the “Google matrix” G is the transition matrix of the surfer’s Markov chain. Every entry of G is at least (1 − d)/n > 0, so by the Perron–Frobenius theorem the chain has exactly one stationary distribution, and r is it; the ranks are positive and sum to 1.

The power method starts from the uniform vector and applies G repeatedly. Each application shrinks the L1 distance to r by at least a factor d, so the change between iterations is at most 2d^k−1 at iteration k. That gives the guaranteed iteration count shown in the lab, which grows like 1/(1 − d): raise d from 0.85 to 0.99 and the bound grows about sixteenfold. Small, well-connected graphs like these presets often converge faster, because the second-largest eigenvalue of G can be well below d; when a graph contains two or more closed groups of pages that no link leaves, it equals d and the bound is tight. The convergence chart shows the actual changes under the dashed bound.

Brin and Page’s 1998 paper suggested d = 0.85 and wrote the formula as PR(A) = (1 − d) + d Σ PR(T)/C(T), without dividing 1 − d by n; in that form the ranks average 1 instead of summing to 1. The ordering is the same.

The random surfer as a Monte Carlo method

Because r is the stationary distribution of a Markov chain, the ergodic theorem says the fraction of time one long walk spends on each page converges to r. Simulating the walk is therefore a Monte Carlo estimate of PageRank. It needs only local steps and random numbers, and Monte Carlo methods of this kind are used to approximate PageRank on very large or changing graphs, but its error falls only like 1/√steps, and consecutive visits are correlated, so it needs more steps than independent samples would. See Monte Carlo error and the Markov chain simulation for the general picture.

The lab’s surfer uses the same rules as the power method: with probability d it follows a random out-link, otherwise, or when the page has no out-links, it jumps to a page chosen uniformly. Treating dangling pages this way is one of several conventions; others remove dangling pages first, give them a self-link, or send the surfer to a personalized set of pages. Langville and Meyer compare them.

Example result

On the 8-page toy web with d = 0.85 and ε = 10⁻¹⁰, power iteration stopped after 49 iterations, well inside the guaranteed 147, and the ranks sum to 1.000000000000. Page C ranks highest with 0.2856. With seed 42 the random surfer spent 0.2865 of its 100,000 steps on that page, and the L1 distance between the surfer’s visit shares and the power-iteration ranks is 0.0035.

Implementation

The page runs simulation.js from the package below; the Python file is a line-by-line port with the same random-number generator, so a given seed produces the same result in both languages. The excerpts show the core of each.

// PageRank by power iteration. With probability d the surfer follows one of the current
// page's out-links chosen uniformly; otherwise (probability 1 − d) it jumps to a page
// chosen uniformly. A dangling page (no out-links) sends all of its rank to every page
// uniformly, as if it linked to all of them.
export function powerIteration(links, d, tol, maxIter = MAX_ITERATIONS) {
  const n = links.length;
  let r = new Array(n).fill(1 / n);
  const history = [];
  let it = 0, resid = Infinity;
  while (it < maxIter && !(resid < tol)) {
    let dangling = 0;
    for (let i = 0; i < n; i++) if (links[i].length === 0) dangling += r[i];
    const base = (1 - d) / n + (d * dangling) / n;
    const next = new Array(n).fill(base);
    for (let i = 0; i < n; i++) {
      const out = links[i];
      if (out.length === 0) continue;
      const share = (d * r[i]) / out.length;
      for (const j of out) next[j] += share;
    }
    resid = 0;
    for (let i = 0; i < n; i++) resid += Math.abs(next[i] - r[i]);
    r = next;
    it++;
    history.push(resid);
  }
  return { rank: r, iterations: it, residual: resid, history };
}

// The random surfer itself: count visits over many steps. Visit shares converge to PageRank.
export function createSurfer(links, rng) {
  return { links, rng, page: rng.int(links.length), visits: new Array(links.length).fill(0), steps: 0 };
}
export function walk(s, d, k) {
  const { links, rng } = s;
  for (let t = 0; t < k; t++) {
    const out = links[s.page];
    if (rng.uniform() < d && out.length > 0) s.page = out[rng.int(out.length)];
    else s.page = rng.int(links.length);
    s.visits[s.page]++;
    s.steps++;
  }
}

def power_iteration(links, d, tol, max_iter=MAX_ITERATIONS):
    """Follow a random out-link with probability d, else jump to a uniform page.
    A dangling page (no out-links) spreads its rank uniformly over all pages."""
    n = len(links)
    r = [1 / n] * n
    it, resid = 0, math.inf
    while it < max_iter and not resid < tol:
        dangling = 0.0
        for i in range(n):
            if not links[i]:
                dangling += r[i]
        base = (1 - d) / n + d * dangling / n
        nxt = [base] * n
        for i in range(n):
            out = links[i]
            if not out:
                continue
            share = d * r[i] / len(out)
            for j in out:
                nxt[j] += share
        resid = 0.0
        for i in range(n):
            resid += abs(nxt[i] - r[i])
        r = nxt
        it += 1
    return r, it, resid


def random_surfer(links, d, steps, rng):
    """Count visits of a surfer who follows links with probability d and teleports otherwise."""
    n = len(links)
    page = rng.int(n)
    visits = [0] * n
    for _ in range(steps):
        out = links[page]
        if rng.uniform() < d and out:
            page = out[rng.int(len(out))]
        else:
            page = rng.int(n)
        visits[page] += 1
    return visits

Run the full model from a terminal:

node simulation.js --graph toy-web --damping 0.85 --seed 42
python simulation.py --graph toy-web --damping 0.85 --seed 42

Download the model

Assumptions & limitations

• Uniform choices. The surfer picks each out-link of a page with equal probability and teleports to every page with equal probability. Search engines weight both by many other signals.
• Dangling pages teleport uniformly. A page with no out-links behaves as if it linked to every page, which keeps the ranks summing to 1.
• Small fixed graphs. The presets have six or eight pages so that every link and rank can be seen; self-links and repeated links are not modeled.
• Stopping rule. Power iteration stops when the L1 change between iterations drops below ε (or after 1,000 iterations). The distance to the exact vector is then at most ε · d/(1 − d).

Related simulations

• OS-014Markov chainA process that remembers only its current state: stationary distribution, mixing and absorption, live.
• OS-031Random network (Erdős–Rényi)Link every pair at random: Poisson degrees, and a giant component that appears suddenly at mean degree 1.
• OS-012Random walkCoin-flip steps on a line or grid: distance grows like √n, and in 1-D and 2-D every walker comes back.
• OS-032Epidemic on a networkSIR spreading along the edges of random, small-world and scale-free networks, compared with homogeneous mixing.

Background: How Accurate Is a Monte Carlo Estimate?

References

1. Brin, S. & Page, L. (1998). The anatomy of a large-scale hypertextual Web search engine. Computer Networks and ISDN Systems, 30(1–7), 107–117. doi.org/10.1016/S0169-7552(98)00110-X
2. Langville, A. N. & Meyer, C. D. (2006). Google’s PageRank and Beyond: The Science of Search Engine Rankings. Princeton University Press.
3. Newman, M. E. J. (2018). Networks, 2nd ed. Oxford University Press.