PageRank

A query against billions of web pages matches millions of them, and a search engine has to decide which to show first. PageRank orders pages by their links alone: a page is important when important pages link to it. The definition is circular, and resolving it leads to a random walk on the link graph, to the leading eigenvector of a stochastic matrix and to an iteration simple enough to run on a graph that fits on no single machine. This page builds the walk, shows the two ways the plain version breaks, repairs them with damping and teleportation, proves how fast power iteration converges, solves small cases exactly, writes one iteration as a MapReduce job and personalizes the ranking. A four-page example is computed by hand with every intermediate value shown, the method is implemented in NumPy, and everything is checked against networkx on a generated web graph and on an open airline route network, where PageRank is also compared with the plain count of incoming routes. Afterwards you will be able to compute PageRank by hand for a small graph, implement it for a large one, and recognize the shortcuts that make published PageRank numbers wrong. It builds on MapReduce.

To run the code in this topic, install the base group, and the data group for the comparison with networkx.

Intuition

Picture a surfer who starts on a random page and clicks forever, each time choosing one of the page's links at random. In the long run the surfer spends a fixed fraction of the time on each page, and that fraction is the page's PageRank. A page that many pages link to is visited often. A page linked from one frequently visited page that has no other links is visited almost as often as that page itself. A link therefore works like a vote whose weight is the voter's own rank, split evenly among all its links.

The plain walk breaks in two ways:

• A dead end, a page without out-links such as a PDF or a page whose links were never crawled, leaves the surfer with nowhere to go.
• A spider trap, a group of pages that link only to each other, lets the surfer in but never out, so in the long run the trap holds all the rank.

In the upper graph every surfer who reaches R is stuck, so the rank that flows into R disappears from the computation. In the lower graph every surfer who reaches R or S stays there forever. Both graphs return under Pitfalls with the numbers that show the damage.

The repair is a surfer who gets bored. At every step, with probability d, the damping factor and usually 0.85, the surfer follows a random link, and otherwise teleports to a page drawn from a fixed distribution: uniform for ordinary PageRank, or concentrated on chosen pages for personalized PageRank. On a dead end the surfer jumps as well.

The diagram shows one step. The orange branch is teleportation, which can happen on every page, the amber branch is the dead-end jump, and the blue path is an ordinary click.

Instead of following one surfer, follow a crowd. If r(j) is the share of the crowd on page j, then after one step page i holds the shares that arrive along its in-links plus its part of the teleporting and stranded surfers. That update is a matrix times a vector, PageRank is the vector the update leaves unchanged, and computing it by repeating the update is power iteration.

How it works

Notation

A link graph has N pages, and j → i means that page j links to page i. Vectors are columns, and a distribution is a vector with non-negative entries that sum to one.

• The out-degree c of page j is the number of distinct pages it links to.
• The link matrix M is N by N, with the entry in row i and column j equal to 1 / c(j) when j links to i and 0 otherwise.
• The dead-end indicator a has a 1 for every page without out-links and 0 elsewhere.
• The dead-end distribution u says where a surfer on a dead end goes.
• The matrix S is M with its dead ends repaired.
• The damping factor d is the probability of following a link, at least 0 and below 1.
• The teleport distribution v is uniform, 1 / N on every page, unless the ranking is personalized.
• The Google matrix G combines S with teleportation.
• The PageRank vector r is a distribution over the pages.
• The bold 1 in the formulas is the vector of ones, so its transpose times x is the sum of the entries of x, and the L1 norm of x is the sum of their absolute values.

The formula images write the page as a subscript and the step number as a superscript in parentheses. In the text, r(i) is the rank of page i, c(j) the out-degree of page j, and r0, r1 and r2 are the rank vectors after zero, one and two steps of an iteration.

The random walk and the link matrix

The link matrix holds one column per page, the page the surfer is leaving:

Let X after k clicks be the page the surfer is on, and let the vector r after k clicks hold the probability of each page. The law of total probability sums over the page the surfer came from, and only pages that link to i contribute:

Column j of M is the distribution of the next page for a surfer on page j. A column with c(j) > 0 holds c(j) entries equal to 1 / c(j) and sums to one, so M is column-stochastic apart from the columns of dead ends. A distribution that one step leaves unchanged satisfies

which is the circular definition made precise: a page's rank is the sum of the ranks of the pages linking to it, each divided by that page's out-degree. Algebraically, r is an eigenvector of M with eigenvalue 1.

The index order matters: the entry in row i and column j is the probability of moving to i from j, and the denominator is the out-degree of the page the link leaves. Markov chain texts often use the row-stochastic transition matrix, the transpose of M, with the distribution as a row vector on the left. That is the same equation transposed. Linear algebra for machine learning covers eigenvectors, and Probability and statistics the law of total probability.

Dead ends and spider traps

A dead end has an all-zero column. Summing the update over all pages shows what that does to the total:

Whatever rank sits on dead ends vanishes at the next step. If a dead end can be reached from every page, the total keeps shrinking and every rank tends to zero.

A spider trap is a set of pages with no link leaving the set. Pages in the trap send all their rank to pages in the trap, and pages outside may send some in, so the rank inside never decreases. When the trap can be reached from everywhere, all the rank ends up there. A trap that is a cycle adds a second failure: with all the rank on one page of a two-page cycle, the walk hands the whole rank back and forth forever and the iteration never converges. With several traps, every one of them supports its own stationary distribution, so r = M r has no unique solution.

These are the three conditions of the Perron-Frobenius theorem for Markov chains: a column-stochastic matrix that is irreducible (every page reachable from every page) and aperiodic has exactly one stationary distribution, it is positive, and repeated multiplication converges to it from every starting distribution. Dead ends break stochasticity, traps break irreducibility, and a trap that is a cycle breaks aperiodicity. The next two steps repair all three.

Repairing dead ends

Give every dead end the column u:

Now every column sums to one, because the columns of M sum to one except at the dead ends, which u fills exactly:

The usual choices are the uniform distribution and u = v, the teleport distribution, which is the default of networkx. Two other remedies appear in the literature: removing dead ends before the computation and adding them back afterwards, which changes the ranks of the remaining pages, and giving each dead end a link to itself, which turns it into a one-page spider trap.

Damping, teleportation and the Google matrix

The bored surfer follows S with probability d and teleports with probability 1 - d:

G is column-stochastic, since every column sums to d plus (1 - d) times the sum of v, which is one. If every entry of v is positive, every entry of G is positive: every page can reach every page in one step, so the chain is irreducible and aperiodic, and Perron-Frobenius guarantees a unique positive PageRank vector that power iteration finds from any start. PageRank is defined as that vector. Because its entries sum to one, the teleport term simplifies:

With uniform v and u the same equation reads, one page at a time,

Read it as bookkeeping. Damping takes the fraction 1 - d of every page's rank away; teleportation hands exactly that amount back, spread according to v; the rest flows along links, and the rank of dead ends is spread according to u. The first and the last terms are the same for every page, so with uniform v and u every page receives a common share before anything arrives along its in-links:

A page that nobody links to receives exactly this share and nothing else, so all such pages tie at the lowest rank in the graph. The hand solution of the worked example below uses the same quantity as an extra unknown.

G is dense and never needs to be built. For any vector x, its product with G splits into one pass over the links, a dead-end correction and a teleport term:

That costs one pass over the links plus work proportional to N. pagerank_step computes exactly this.

Power iteration and its rate of convergence

Start from any distribution, usually the uniform one, and multiply by G again and again. The error shrinks at least geometrically. Let the error e after k steps be the difference between the iterate and PageRank. Since G r = r, the error obeys the same update, and because both vectors sum to one, the error sums to zero and the teleport term drops out:

S never increases the L1 norm, because its entries are non-negative and its columns sum to one:

So every step multiplies the error by at most d, and the initial error is at most 2, because two distributions are at most 2 apart in the L1 norm:

The error shrinks by at least the factor d per step, whatever the size of the graph. Reaching an error ε takes at most

iterations, which iterations_needed computes. For ε = 10⁻⁸ that is 28 iterations at d = 0.5, 118 at 0.85, 373 at 0.95 and 1,902 at 0.99.

The exact rate is set by the eigenvalues. Any eigenvector of S whose eigenvalue λ is not 1 has entries that sum to zero, and then the teleport term vanishes from its product with G:

So the eigenvalues of G are 1 and d times the other eigenvalues of S. The error decays like the k-th power of d λ2, where λ2 is the largest modulus among the other eigenvalues of S. It is at most 1, and exactly 1 when S has two or more closed groups of pages, groups that no link leaves. Real link graphs have many such groups, so on them the rate is exactly d. The airline route network below has seven and converges at rate d; a generated web graph with none apart from its dead ends converges much faster than the bound.

The error cannot be measured during the run, but the residual δ, the L1 distance between two successive iterates, can. Since the error after a step is at most d times the error before it, and the two errors differ by at most δ, the residual bounds both:

Stopping when the residual falls below a tolerance τ therefore guarantees an error below τ d / (1 - d), which is 5.67 τ for d = 0.85 and 99 τ for d = 0.99.

The exact solution

The PageRank equation is a linear system:

I - dS is invertible for d < 1, because by the contraction above, applying it to any nonzero x leaves an L1 norm of at least (1 - d) times that of x. Expanding the inverse as a geometric series, the Neumann series, gives

This is the surfer again. S to the k times v is where a surfer who has just teleported is after k more clicks, and (1 - d) times d to the k is the probability that exactly k clicks have passed since the last teleport. The series shows directly that r is non-negative and sums to one. The number of clicks between teleports is geometric with mean d / (1 - d), about 5.7 for d = 0.85.

When dead ends follow the teleport distribution, u = v, the rank of the dead ends joins the teleport term, so r is a multiple of the solution of the same system with the bare link matrix M in place of S and v as the right-hand side. Normalizing that solution to sum one gives r without building S at all; exact_pagerank_without_repair does this.

Gaussian elimination costs time proportional to N³ and memory proportional to N². That is instant for a few thousand pages and impossible for billions, which is why the web-scale computation is power iteration, whose step costs time proportional to the number of pages plus the number of links.

The simplified update without teleportation

A shortcut seen in hand-worked examples keeps the damping factor on the incoming shares and drops the teleport term:

On a graph without dead ends the total after k rounds is exactly d to the k: 1, 0.85, 0.7225, 0.6141 and so on for d = 0.85. Dead ends make it shrink faster. Every rank tends to zero, so the numbers after a few rounds are not PageRank, and rescaling them to sum one each round does not help: that is the undamped walk r ← M r, with its dead ends and spider traps. The teleport term is what returns the rank that damping removes.

The 1998 description of PageRank uses a second scale, whose ranks sum to N on a graph without dead ends, although the same paper says they sum to one:

Either scale is consistent on its own: the teleport term must be (1 - d) times the total rank divided by N, which is (1 - d) / N for ranks that sum to one and 1 - d for ranks that sum to N.

PageRank as MapReduce

On a cluster the graph is a set of records, one per page j, holding its rank r(j) and the list of pages it links to. One iteration is one MapReduce job followed by a map-only step:

1. Map. For the record of page j, emit the page's own links under its own key, and for every page i in its link list emit the share r(j) / c(j) under key i.
2. Shuffle. Group all emitted values by page.
3. Reduce. For page i, add the shares to get the incoming rank, which is entry i of M r, take the page's links from the links value, and write the record back.
4. Dead ends and teleportation. A dead end's rank never leaves its mapper, so the driver measures the missing rank m, the total before the round minus the total that arrived (in Hadoop with a counter), and a map-only step adds the teleport share and the missing rank back.

Here T is the total rank, one. Step 4 makes the round exactly one multiplication by G with uniform u and v; a personalized version replaces T / N by T v(i) and m / N by m u(i), with u and v small enough to send to every mapper. MapReduce jobs keep no state between rounds, which is why the mapper must emit the links: they are the only way the graph reaches the next round.

The blue path is the rank job, the amber node and edges are the driver's dead-end bookkeeping, and the green map-only step finishes the round.

Each round shuffles one share per link plus every page's link list, which holds one entry per link as well and crosses the network in every round although it never changes; a plain Hadoop job also writes every round to the distributed file system. With 50 to 100 rounds, that traffic dominates. Three refinements are standard. A combiner adds the shares a mapper emits for the same page before the shuffle, which is valid because addition is associative and commutative. Spark keeps the link lists partitioned by page and cached in memory, so that only the ranks move. Vertex-centric systems such as Pregel keep the graph in place and send only messages along the links. MapReduce covers the programming model and Distributed storage and compute the systems.

Personalized PageRank

Replacing the uniform v by a distribution concentrated on a seed set, such as a user's bookmarks, the pages of one topic or a single page, gives personalized PageRank. Every teleport lands on the seeds, so by the Neumann series the rank of page i is the probability that a walk from the seeds, of geometric length, ends on i: pages close to the seeds rank high. This is the random walk with restart used to recommend accounts to follow, to find related items and to cluster a graph locally around a node.

For a fixed dead-end distribution u, the personalized vector is (1 - d) times the inverse of I - dS times v, which is linear in v:

Precomputing the ranks for a set of basis distributions, one per topic or one per important page, then lets any mixture be answered at query time without another iteration. With u = v the dead-end columns change with v and the map is no longer linear.

Worked example

Four pages: A links to B, C and D, B links to C, C links to A and B, and D has no out-links. The damping factor is d = 0.85 and v and u are uniform, so the teleport share (1 - d) / N is 0.0375.

D, in amber, is the dead end. Every value below is computed in double precision and rounded to four decimals for display. A rounded vector can sum to 0.9999 or 1.0001; at full precision every rank vector here sums to one.

The matrices

The out-degrees are 3, 1, 2 and 0. Column A of M holds 1/3 for B, C and D, column B holds 1 for C, column C holds 1/2 for A and B, and column D is empty, so the columns of M sum to 1, 1, 1 and 0. Repairing D with the uniform u fills column D with 0.25, and every column of S sums to one. Each entry of G is 0.85 times the entry of S plus 0.0375, which gives the rows

• A: 0.0375, 0.0375, 0.4625, 0.25
• B: 0.3208, 0.0375, 0.4625, 0.25
• C: 0.3208, 0.8875, 0.0375, 0.25
• D: 0.3208, 0.0375, 0.0375, 0.25

with the columns in the order A, B, C, D. Column D of G is exactly uniform, 0.85 × 0.25 + 0.0375 = 0.25: a surfer on D goes anywhere with equal probability, bored or not. No entry is zero, so the PageRank vector exists, is unique and is positive.

The first step, as one MapReduce round

Start from r0 = (0.25, 0.25, 0.25, 0.25). The mappers emit each page's links and its shares, its rank divided by its out-degree:

• A, rank 0.25, links B, C and D: emits A with its links, and the shares 1/12 to B, 1/12 to C and 1/12 to D.
• B, rank 0.25, links C: emits B with its links, and the share 1/4 to C.
• C, rank 0.25, links A and B: emits C with its links, and the shares 1/8 to A and 1/8 to B.
• D, rank 0.25, no links: emits D with an empty link list and no share.

The reducers add the shares that reach each page. D's rank of 0.25 reached nobody, so the missing rank is m = 0.25 and every page gets m / N = 1/16 = 0.0625 of it back. The map-only step then computes 0.0375 + 0.85 × (incoming + 0.0625) for every page:

• A receives 1/8, so its incoming rank is 0.1250 and its new rank 0.0375 + 0.85 × 0.1875 = 0.1969.
• B receives 1/12 + 1/8 = 0.2083, and its new rank is 0.0375 + 0.85 × 0.2708 = 0.2677.
• C receives 1/12 + 1/4 = 0.3333, and its new rank is 0.0375 + 0.85 × 0.3958 = 0.3740.
• D receives 1/12 = 0.0833, and its new rank is 0.0375 + 0.85 × 0.1458 = 0.1615.

The products are taken with the exact fractions 13/48, 19/48 and 7/48; multiplying the rounded sums instead gives 0.3739 for C and 0.1614 for D, one unit lower in the last digit. The same vector r1 = (0.1969, 0.2677, 0.3740, 0.1615) is G times r0, the first step of power iteration, and its residual is 0.0531 + 0.0177 + 0.1240 + 0.0885 = 0.2833.

The second step

For page A, the shares come from C, half its rank, and from D through the dead-end repair, a quarter of its rank:

With the four-decimal values 0.1870 + 0.0404 the same line gives 0.2308, which is why more digits are carried here. The whole vector is r2 = (0.2307, 0.2865, 0.3551, 0.1276), with residual 0.1054.

The exact solution

The system (I - dS) r = (1 - d) v has the right-hand side 0.0375 in every row, and the rows of I - dS are

• A: 1, 0, -0.425, -0.2125
• B: -0.2833, 1, -0.425, -0.2125
• C: -0.2833, -0.85, 1, -0.2125
• D: -0.2833, 0, 0, 0.7875

By hand it is easier to notice that every page receives the same common share s, the teleport share plus a quarter of D's damped rank. Treat s as an unknown, express every rank through it, and fix s at the end by normalization. With 0.85 / 3 = 0.2833:

The equations for A and B give r(B) = r(A) + 0.2833 r(A) = 1.2833 r(A), and then r(C) = s + (0.2833 + 0.85 × 1.2833) r(A) = s + 1.3742 r(A). Substituting into the equation for A gives r(A) = 1.425 s + 0.5840 r(A), so r(A) = 1.425 s / 0.4160 = 3.4257 s, and then r(B) = 4.3963 s, r(C) = 5.7074 s and r(D) = 1.9706 s. These factors are computed at full precision; repeating the steps with the four-decimal values shown moves them by a few units in the last digit, starting with 1.425 / 0.4160 = 3.4255. They sum to 15.4999 s, so s = 0.0645 and

• r(A) = 0.2210
• r(B) = 0.2836
• r(C) = 0.3682
• r(D) = 0.1271

As a check, 0.0375 + 0.2125 × 0.1271 = 0.0645 recovers s. C ranks first: it collects all of B's rank and a third of A's. B is second: it receives the same half of C's rank as A, plus a third of A's. D, linked only from A, ranks last but keeps more than the floor 0.0375 because A gives it a third of its rank.

How fast the iteration converges

Power iteration started from the uniform vector reaches a residual below 10⁻¹² after 45 iterations and agrees with the exact solution to 10⁻¹³. The bound 2 × 0.85 to the k guarantees an error below 10⁻¹² only after 175 iterations. The iteration is faster because the eigenvalues of S are 1, 0.2085, -0.3065 and -0.6520, so the second-largest modulus among the eigenvalues of G is 0.85 × 0.6520 = 0.5542, and the measured error shrinks by exactly that factor per step once the other components have died out. The negative sign of that eigenvalue makes the error alternate: A's rank goes 0.1969, 0.2307, 0.2155 around its limit 0.2210.

The simplified update on the same graph

With the update r ← 0.85 M r the totals are 1, 0.6375, 0.4817, 0.3838, 0.2973 and 0.2342 for rounds 0 to 5. Round 1 is 0.85 × (1 - 0.25) = 0.6375: the factor d and D's lost rank together. On a graph without dead ends the totals would be the powers of 0.85.

Personalized on page B

With v and u both concentrated on B, the ranks are 0.1647 for A, 0.4011 for B, 0.3876 for C and 0.0467 for D. B keeps far more than the teleport share 1 - d = 0.15 because its only link goes to C, and C sends half of what it receives straight back. C stays close behind B, and D, three links away from B, falls from 0.1271 to 0.0467.

Every number in this section is asserted by the tests in tests, mainly test_matrices.py, test_iteration.py, test_exact.py, test_convergence.py and test_mapreduce.py, and printed by examples/worked_example.py and examples/mapreduce_rounds.py.

The code

The package pagerank is plain NumPy, split into one module per idea. networkx is imported only inside the functions of comparisons.py, so everything else works without it.

• graph.py holds LinkGraph, a frozen dataclass with the page names and the links as two index arrays, sorted and without duplicates, with from_links, from_edges, the degrees and the dead ends.
• distributions.py turns weights given by name, by position or not at all into the distributions v and u, and checks rank vectors and the damping factor.
• matrices.py builds M, S and G as dense arrays for small graphs and sorts eigenvalues by modulus.
• iteration.py is the heart of the topic: propagate computes M x from the link list, pagerank_step computes G x without forming G, power_iteration returns the ranks, the residual of every step and, on request, every iterate, and personalized_pagerank teleports to seed pages.
• exact.py builds the linear system and solves it, with and without the dead-end repair.
• convergence.py holds the bound 2 d to the k, iterations_needed, the error bound a residual gives and the rate measured late in a run.
• components.py finds strongly connected components with Kosaraju's two-pass depth-first search and lists the closed groups that make the second eigenvalue exactly d. Search algorithms covers depth-first search.
• mapreduce.py holds the mapper, the reducer, the shuffle, a tiny in-memory engine that keeps every intermediate list, and full rounds with the dead-end and teleport step.
• reporting.py prints matrices, rank vectors and a whole MapReduce round in the order of a hand calculation.
• ranking.py turns scores into places with ties broken by name and compares two rankings: Spearman's correlation, the overlap of their tops, the pages that move most and the share of the total held by the top or the bottom.
• small_graphs.py builds the worked example and the small failure graphs, and computes the common share s.
• pitfalls.py holds the deliberately wrong versions used under Pitfalls.
• generators.py grows directed scale-free web graphs and small random graphs from a seed.
• openflights.py downloads the two OpenFlights files from a pinned commit, checks their SHA-256 digests and parses them.
• comparisons.py converts to and from networkx and runs networkx.pagerank.
• plotting.py draws every figure in the handbook's four colours and saves it reproducibly.

The whole iteration is one function. Shares travel along the link list, the rank of dead ends is spread by u, and the teleport term restores what damping removed:

def pagerank_step(graph, ranks, damping=DEFAULT_DAMPING, teleport=None, dangling=None):
    ranks = as_ranks(graph, ranks)
    teleport_vector, dangling_vector = teleport_and_dangling(graph, teleport, dangling)
    dangling_rank = ranks[graph.dangling].sum()
    linked = propagate(graph, ranks) + dangling_rank * dangling_vector
    return damping * linked + (1.0 - damping) * ranks.sum() * teleport_vector

The map and reduce functions are plain generators over key-value pairs, in the form any MapReduce engine accepts:

def map_page(page, value):
    rank, links = value
    yield page, ("links", links)
    for target in links:
        yield target, ("share", rank / len(links))


def reduce_page(page, values):
    links = ()
    incoming = 0.0
    for kind, payload in values:
        if kind == "links":
            links = payload
        else:
            incoming += payload
    yield page, (incoming, links)

The examples and the project import the package, so install the repository first as described in the main README. Each example demonstrates one idea and runs in a few seconds from the repository root:

• examples/worked_example.py prints every value of the worked example: the matrices, the first two steps, the exact solution with the common share, the eigenvalues, the simplified update and the ranks personalized on B.
• examples/mapreduce_rounds.py prints the first MapReduce round of the worked example pair by pair, runs 40 rounds on a generated web graph of 5,000 pages and checks them against power iteration to 5.4 × 10⁻¹⁵, and shows what a mapper that forgets the links loses.
• examples/failure_modes.py shows the dead end leaking rank and the spider trap absorbing it, with and without damping, and saves the figure shown under Pitfalls.
• examples/common_mistakes.py demonstrates the simplified update, the mixed scales, the wrong degree and personalizing on a dead end, and saves the rank-leak figure.
• examples/convergence.py measures the residual of power iteration on the route network and the generated graph for four damping factors and saves the convergence figure shown under In practice.
• examples/compare_with_networkx.py compares our ranks with networkx.pagerank on both larger graphs, with and without personalization, and shows what the default tolerance of networkx does to the top ten.

python data-at-scale/pagerank/examples/worked_example.py
python data-at-scale/pagerank/examples/mapreduce_rounds.py
python data-at-scale/pagerank/examples/failure_modes.py
python data-at-scale/pagerank/examples/common_mistakes.py
python data-at-scale/pagerank/examples/convergence.py
python data-at-scale/pagerank/examples/compare_with_networkx.py

The sample project, project/airport_ranking.py, ranks the world's airports. It downloads the OpenFlights route and airport files, verifies them, collapses the airlines into one directed link per ordered pair of airports, runs power iteration, and compares the result with the simplest alternative, the number of airports that fly in. It then personalizes the ranking on one airport, Auckland unless --airport names another, and saves two figures. Options such as --damping, --tolerance and --top change the run, --data points at another download folder, and --figures sends the PNGs elsewhere so a custom run does not overwrite the ones shown here. The default run takes about a second once the files are downloaded.

The global ranking and the in-degree meet in the comparison, while the personalized ranking goes straight into the report and its own figure.

python data-at-scale/pagerank/project/airport_ranking.py
python data-at-scale/pagerank/project/airport_ranking.py --airport NBO --figures /tmp/nairobi

With the defaults, the route graph has 3,425 airports and 37,594 directed links; 16 airports have no departures and 7 have no arrivals. Power iteration needs 130 iterations to reach a residual below 10⁻¹². The two rankings agree broadly, with a Spearman correlation of 0.8438 over all airports, nine airports in both top tens and 38 in both top fifties, but they disagree about which hubs matter most. Within the PageRank top 50 the biggest climbers, from their place by in-degree to their place by PageRank, are Bethel in Alaska (BET) from 415 to 44, Buenos Aires Aeroparque (AEP) from 222 to 43, Brisbane (BNE) from 159 to 49 and Bogota (BOG) from 111 to 20. The biggest fallers are Barcelona (BCN) from 16 to 39, London Gatwick (LGW) from 15 to 38, Rome Fiumicino (FCO) from 18 to 40 and Munich (MUC) from 9 to 24. Bethel shows the mechanism in its purest form: only 21 airports fly in, but they serve a median of 2 destinations each, so most of them pass Bethel half of their rank or all of it. The 163 airports that fly into Barcelona serve a median of 57 destinations, so each passes on only a small share.

PageRank grows roughly in proportion to in-degree, but airports with the same in-degree differ by up to a factor of 7.7. The distribution is heavy-tailed: the top 1 % of airports, 34 of them, hold 0.1106 of the total rank, the bottom half holds 0.1588, and the median airport has about half the average rank.

Personalizing on Auckland pulls its region to the top. Auckland itself keeps 0.1979 of the rank, then come Wellington, Christchurch, Sydney, Brisbane, Melbourne, Nadi, Palmerston North, Singapore and Papeete; Palmerston North sits in place 847 of the global ranking. Personalizing on Nairobi instead ranks Nairobi, Johannesburg, Addis Ababa, Dubai, Istanbul, Paris, Dar es Salaam, Eldoret, Lusaka and Cairo first, with the global hubs mixed into the regional ones.

The notebook pagerank.ipynb is a guided tour in the order of this page: the matrices, power iteration, the exact solution and one MapReduce round on the worked example, personalized ranks, the same computations on a generated web graph of 5,000 pages, one section per failure and pitfall, and the airline route network with the comparison against networkx. The tests in tests check the worked example value by value, the mathematical properties above, the components against networkx and the ranks against networkx.pagerank, and run in a few seconds:

python -m pytest data-at-scale/pagerank

Data:

• The generated web graph comes from scale_free_web_graph, the directed preferential-attachment model of Bollobás, Borgs, Chayes and Riordan, with a fixed seed, so no download or licence is involved. With 5,000 pages it has 9,089 links, 562 dead ends, 3,785 pages without in-links and one page with 1,538 in-links.
• The airline route network is the OpenFlights route database (67,663 routes as of June 2014) and its airport database, downloaded on first use from the OpenFlights GitHub repository at a pinned commit into the repository's .data/pagerank/ folder and verified against SHA-256 digests. Both are made available under the Open Database License (ODbL) 1.0, with the individual contents under the Database Contents License 1.0. The results and figures on this page contain information from OpenFlights, which is made available under the ODbL.

In practice

networkx.pagerank computes the same vector with power iteration on a SciPy sparse matrix. Its alpha is the damping factor d, and dead ends follow the personalization vector unless dangling says otherwise, as in pagerank_step:

import networkx as nx

from pagerank import load_openflights, to_networkx

routes, airports = load_openflights()
scores = nx.pagerank(to_networkx(routes), alpha=0.85, tol=1e-13, max_iter=10_000)

With a tight tolerance it agrees with power_iteration to 1.1 × 10⁻¹¹ on the generated graph and 5.2 × 10⁻¹¹ on the route network, and to 4.3 × 10⁻¹¹ with personalization on two seed airports, Auckland and Nairobi; tests/test_comparisons.py checks a generated graph of 3,000 pages the same way. On the route network, power iteration with d = 0.85 takes a few hundredths of a second. The ten highest-ranked airports, each with its number of incoming routes and its place by that number, are:

1. Atlanta (ATL), PageRank 0.00468, 216 in-links, place 5.
2. Istanbul (IST), 0.00441, 230 in-links, place 4.
3. Chicago O'Hare (ORD), 0.00429, 203 in-links, place 7.
4. Denver (DEN), 0.00426, 168 in-links, place 13.
5. Dallas-Fort Worth (DFW), 0.00419, 185 in-links, place 10.
6. Moscow Domodedovo (DME), 0.00413, 189 in-links, place 8.
7. Paris Charles de Gaulle (CDG), 0.00396, 233 in-links, place 2.
8. Frankfurt (FRA), 0.00386, 238 in-links, place 1.
9. Beijing (PEK), 0.00383, 206 in-links, place 6.
10. Amsterdam (AMS), 0.00366, 231 in-links, place 3.

Frankfurt has the most in-links but ranks eighth, and Denver, thirteenth by in-links, ranks fourth. PageRank weighs each link by the rank of its source divided by that source's out-degree, so a hub fed by many small regional airports that fly almost nowhere else collects nearly their whole rank, while a hub whose neighbours are themselves hubs with hundreds of destinations receives a small share from each.

The figure tests the convergence theory. On the route network, which has seven closed groups of airports, the residual falls at 0.4730, 0.8452, 0.9499 and 0.9900 per step for d = 0.5, 0.85, 0.95 and 0.99, parallel to the bound, and reaching 10⁻¹⁴ takes 39, 158, 497 and 2,536 iterations against the bound's 48, 203, 642 and 3,277. The closed groups are small islands, the largest being ten airports in New Caledonia that fly only to each other and receive no flights from outside; together the seven groups hold 28 airports and 0.0083 of the rank. The generated graph has no closed group besides its dead ends; its second eigenvalue is far below d and it needs 22 to 38 iterations for every d.

When to use which:

• Use the from-scratch version to understand the method, to trace a MapReduce round and to test a distributed implementation on a graph small enough to check.
• Use networkx.pagerank for graphs that fit in memory, up to a few million links. Pass tol explicitly: the default, 10⁻⁶, is multiplied by the number of nodes, so on the route network it stops once the L1 change falls below 3.4 × 10⁻³. Its result is then 6.9 × 10⁻³ away from the converged vector in L1 and puts Dubai tenth instead of Amsterdam.
• igraph's Graph.pagerank (the PRPACK solver) is much faster on large in-memory graphs.
• For graphs that do not fit on one machine, use a distributed engine: Spark GraphX pageRank and GraphFrames pageRank, both parameterized by the reset probability 1 - d, or a vertex-centric system. For a personalized vector of a single node on a huge graph, local push algorithms touch only the neighbourhood of the seed instead of the whole graph.

PageRank is one signal among hundreds in a modern search engine; Search engines combines it with text relevance, and personalized PageRank is a common baseline for the recommendations of Recommender systems.

Pitfalls

• Dividing by the wrong degree. The entry of M in row i and column j uses 1 / c(j), the out-degree of the page the link leaves. Dividing by the in-degree of the target, an easy slip when the matrix is filled row by row, makes the rows sum to one instead of the columns. The uniform vector is then a fixed point of the update, and since it is positive it is the answer: on the worked example every page gets 0.25, whatever the links. Check that the columns of M sum to one, or to zero for dead ends. examples/common_mistakes.py prints both sums and the uniform answer.
• Ignoring dead ends. Without the repair, rank that reaches a dead end disappears. On three pages where P links to Q, Q links to P and R, and R has no out-links, the total falls 1, 0.6667, 0.5, 0.3333, 0.25 and halves every two steps from there. Large crawls are full of dead ends, from documents without links to pages whose links were never fetched.
• Iterating without damping. On four pages where P links to Q and R, Q links to P, and R and S link only to each other, the undamped walk puts 0.9995 of the rank on R and S after 20 steps, and started with all the rank on R it alternates between R and S forever. With d = 0.85 the iteration converges and the trap holds 0.8077. examples/failure_modes.py draws both failures:

On the left the bare link matrix loses rank at every step while the repaired matrix keeps the total at one. On the right the undamped trap swallows almost everything and the walk started on R never settles, while damping caps the trap's share at 0.8077.

• Dropping the teleport term. The update r ← d M r, a shortcut sometimes used to keep hand calculations short, multiplies the total rank by d every round on a graph without dead ends and by less than d with them: 1, 0.85, 0.7225, 0.6141 on the worked graph with a link from D back to A, and 1, 0.6375, 0.4817, 0.3838 on the worked graph itself. Two rounds give A 0.1204, B 0.1505, C 0.1806 and D 0.0301, which are not PageRank values on any scale. Rescaling does not fix it, because the rescaled iteration is the undamped walk: after 12 rounds it gives 0.2197, 0.2987, 0.4027 and 0.0790 against PageRank's 0.2210, 0.2836, 0.3682 and 0.1271. examples/common_mistakes.py shows the totals:

Only the full update keeps the total at one; without dead ends the simplified update follows the dashed powers of 0.85 exactly, and with D's lost rank it falls faster still.

• Mixing the two scales. The term (1 - d) / N belongs to ranks that sum to one and 1 - d to ranks that sum to N. Starting at one per page and adding (1 - d) / N still converges to PageRank, but the total after k rounds is 1 + (N - 1) times d to the k, so the values after two rounds, A 0.8078, B 0.9070, C 1.0433 and D 0.4094 on the graph with the link from D to A, total 3.1675 and are neither PageRank nor N times PageRank. Comparing with a library that returns ranks summing to one requires dividing the ranks of the second scale by N; examples/common_mistakes.py prints both.
• A mapper that does not emit the links. A reducer sees only the keys that received values. If the mapper emits shares alone, the reducer cannot write the page's links into the next round's record, and a page that nobody links to never reaches a reducer at all. One round of such a job on the generated graph keeps 1,215 of 5,000 pages, none of them with links, as examples/mapreduce_rounds.py prints. The short PageRank example distributed with Spark has the same property: after its first round the ranks contain only pages that received a share.
• Personalizing on a dead end. When dead ends follow the teleport vector, the default in networkx, a seed without out-links is absorbing: from D the surfer can only jump back to D, and personalizing the worked example on D gives 0, 0, 0 and 1. With a uniform dead-end distribution the answer is 0.1879, 0.2411, 0.3130 and 0.2581, as examples/common_mistakes.py prints.
• Trusting a loose stopping rule. The residual bounds the error only through the factor d / (1 - d), and the error must be judged against the size of the ranks, which is about 1 / N. A tolerance that is fine for a thousand pages can leave the order of the top results wrong on a million. The default tolerance of networkx changes the tenth place on the route network, as examples/compare_with_networkx.py shows.
• Pushing d towards one. A larger d follows the links more faithfully but slows convergence like 1 / (1 - d), from 158 iterations at d = 0.85 to 2,536 at d = 0.99 on the route network, and moves rank into spider traps: the four-page trap above holds 0.6071 of the rank at d = 0.5, 0.8077 at 0.85, 0.9220 at 0.95 and 0.9829 at 0.99. The value 0.85 is a compromise, not a constant of nature.
• Confusing the parameter names. networkx's alpha and igraph's damping are d; GraphX's resetProb, GraphFrames' resetProbability and the restart probability α of much of the personalized PageRank literature are 1 - d. Passing 0.15 where 0.85 is meant inverts the model.

Further reading

• S. Brin and L. Page, "The anatomy of a large-scale hypertextual Web search engine", Computer Networks and ISDN Systems 30, 107-117, 1998. The search engine and the second scale of the formula.
• L. Page, S. Brin, R. Motwani and T. Winograd, "The PageRank citation ranking: bringing order to the Web", technical report, Stanford InfoLab, 1999. The random surfer, dead ends and personalization.
• A. N. Langville and C. D. Meyer, Google's PageRank and Beyond: The Science of Search Engine Rankings, Princeton University Press, 2006. The mathematics in depth, including dead-end treatments and the sensitivity to d.
• A. N. Langville and C. D. Meyer, "Deeper inside PageRank", Internet Mathematics 1(3), 335-380, 2004.
• T. H. Haveliwala and S. D. Kamvar, "The second eigenvalue of the Google matrix", technical report, Stanford University, 2003. The proof that the second eigenvalue of G has modulus at most d, with equality for graphs with two or more closed groups.
• J. Lin and C. Dyer, Data-Intensive Text Processing with MapReduce, chapter 5, Morgan and Claypool, 2010. Graph algorithms in MapReduce, including the missing-mass step for dead ends.
• J. Leskovec, A. Rajaraman and J. D. Ullman, Mining of Massive Datasets, chapter 5, third edition, Cambridge University Press, 2020. Link analysis, spider traps and link spam.
• T. H. Haveliwala, "Topic-sensitive PageRank", Proceedings of WWW 2002.
• G. Jeh and J. Widom, "Scaling personalized web search", Proceedings of WWW 2003. Linearity of personalized PageRank.
• R. Andersen, F. Chung and K. Lang, "Local graph partitioning using PageRank vectors", FOCS 2006. Local push algorithms.
• D. F. Gleich, "PageRank beyond the Web", SIAM Review 57(3), 321-363, 2015. Uses far from search engines.
• B. Bollobás, C. Borgs, J. Chayes and O. Riordan, "Directed scale-free graphs", SODA 2003. The model behind scale_free_web_graph.
• M. Sharir, "A strong-connectivity algorithm and its applications in data flow analysis", Computers and Mathematics with Applications 7(1), 67-72, 1981. The two-pass algorithm for strongly connected components in components.py.
• G. Malewicz et al., "Pregel: a system for large-scale graph processing", SIGMOD 2010.