PageRank

The text-matching methods of the earlier topics, from TF-IDF to BM25, score a page by its content. On the web, content is easy to manipulate and quality varies enormously, so early web search engines returned many pages that matched a query's words and were useless. The links between pages offered another kind of evidence. A link from one page to another is a small judgment by its author that the target is worth visiting. PageRank (Brin and Page, 1998; Page, Brin, Motwani, and Winograd, 1999) turns the whole web's links into a score of importance for each page, computed once from the link graph a crawler collects and used as one signal in ranking.

This article builds PageRank the way a course in applied linear algebra does. It starts from a thought experiment, writes it as a formula, and then turns the formula into a matrix in three stages: the raw link matrix $H$, the stochastic matrix $S$ that repairs pages without links, and the Google matrix $G$ that adds random jumps. The PageRank vector is the dominant eigenvector of $G$. The eigenvalues of $S$ and $G$ explain why that eigenvector exists, why it is unique, and how fast power iteration finds it. A five-page web is carried through every step, with every matrix entry and intermediate value shown.

The random surfer

PageRank is defined by a thought experiment. A surfer starts on a random page and clicks links forever. At each step, from the current page, the surfer picks one of its out-links at random and follows it. Over a long time, the surfer visits some pages much more often than others: pages with many in-links, and especially pages with in-links from pages that are themselves often visited. A page's PageRank is the long-run fraction of time the surfer spends there.

Following links alone does not quite work. A page with no out-links, called a dangling page, traps the surfer. A group of pages linking only to each other would capture the surfer forever, and pages that link into the group receive nothing back. The fix is teleportation: at each step, with probability $1 - d$, the surfer ignores the links and jumps to a page chosen uniformly at random from all $N$ pages. With probability $d$, called the damping factor, it follows a link as before. From a dangling page, it always teleports. Brin and Page used $d = 0.85$. The number of links followed between two jumps is then geometric, with mean $d/(1-d) \approx 5.67$, so the surfer follows between five and six links, on average, before jumping.

The formula

The PageRank of page $p$ is the probability of being there:

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

where the sum is over pages $q$ that link to $p$ and $L(q)$ is the number of out-links of $q$. Each page divides its PageRank equally among the pages it links to, and every page also receives an equal share of the teleportation. The PageRanks of all pages sum to 1. Brin and Page's paper wrote the first term as $1 - d$, without dividing by $N$, while also stating that the PageRanks sum to 1. With that first term they sum to $N$ instead, which scales every value by $N$ but gives the same ranking.

The formula as written assumes every page has at least one out-link. A dangling page sends the surfer to a random page, so its PageRank is spread evenly over all $N$ pages, adding $d \sum_{q \text{ dangling}} PR(q)/N$ to every page.

The formula defines each page's PageRank in terms of the PageRanks of the pages that link to it, so it is not a recipe but a system of $N$ equations in $N$ unknowns. The rest of this article is about that system: how to write it compactly, why it has exactly one solution, and how to find it.

The five-page example

A small web is used throughout. Page $A$ links to $B$ and $C$, $B$ links to $C$ and $E$, $C$ links to $A$, and $D$ links to $C$. Page $E$ has no out-links, so it is dangling, and nothing links to $D$. Two of the difficulties PageRank has to handle on the real web appear here in miniature: a page that no link reaches, and a page that leads nowhere. The cycle $A \to C \to A$ makes the computation swing before it settles. A third difficulty, a group of pages that traps the surfer, gets its own tiny example below.

The equations, written out

With $N = 5$ and $d = 0.85$, every page receives $0.15/5 = 0.03$ from teleportation and $0.85/5 = 0.17$ of $E$'s PageRank from the dangling page. Call that common part $t = 0.03 + 0.17\,\pi_E$, writing $\pi_p$ for the PageRank of page $p$. A page with two out-links passes $0.85/2 = 0.425$ of its rank along each, and a page with one out-link passes $0.85$. The formula then gives one equation per page:

$$\begin{aligned} \pi_A &= t + 0.85\,\pi_C, \\ \pi_B &= t + 0.425\,\pi_A, \\ \pi_C &= t + 0.425\,\pi_A + 0.425\,\pi_B + 0.85\,\pi_D, \\ \pi_D &= t, \\ \pi_E &= t + 0.425\,\pi_B. \end{aligned}$$

Five equations of this kind are small enough to solve by hand. Since $\pi_D = t$, measure everything in units of $t$ and substitute downward. The second equation gives $\pi_B = t + 0.425\,\pi_A$. Putting that into the fifth gives $\pi_E = 1.425\,t + 0.180625\,\pi_A$, and into the third, $\pi_C = 2.275\,t + 0.605625\,\pi_A$. The first equation then reads $\pi_A = 2.93375\,t + 0.51478\,\pi_A$, so $\pi_A = 6.0462\,t$, and back-substitution gives

$$(\pi_A, \pi_B, \pi_C, \pi_D, \pi_E) = t\,(6.0462,\ 3.5697,\ 5.9368,\ 1,\ 2.5171).$$

The values must sum to 1, and the bracket sums to $19.0698$, so $t = 1/19.0698 = 0.0524$. As a check, $0.03 + 0.17\,\pi_E = 0.03 + 0.17 \times 2.5171 \times 0.0524 = 0.0524$, which is $t$ again. The equations fix the PageRanks only up to a common scale until the sum is imposed; this is the first sign that PageRank is an eigenvector, which is defined only up to scale.

Values are rounded to four decimals. The column without teleportation sets $d = 1$, keeping only the repair of the dangling page, and its exact fractions come from solving the same equations in rational arithmetic.

$A$ ranks highest even though it has a single in-link, from $C$. $C$ has three in-links, but $C$ gives all of its rank to $A$, while the pages linking to $C$ split theirs. A link from an important page that links to little else is worth a great deal. $D$, which nothing links to, still gets $0.0524$: $0.03$ from teleportation and $0.17 \times 0.1320 = 0.0224$ from the dangling page $E$, whose surfer jumps to a random page.

Where the rank flows

At the PageRank vector, the rank sent along each link is $d\,\pi_q / L(q)$. $C$ sends $0.85 \times 0.3113 = 0.2646$ to $A$. $A$ sends $0.1348$ to each of $B$ and $C$, $B$ sends $0.0796$ to each of $C$ and $E$, and $D$ sends $0.0446$ to $C$. $E$ sends $0.0224$ to every page, and teleportation adds $0.03$ to every page. $A$'s PageRank is then $0.03 + 0.0224 + 0.2646 = 0.3170$, which is $0.3171$ before the parts are rounded, and the other pages add up the same way. The balance holds at every page at once, which is what it means for the distribution to be stationary.

What goes wrong without the fixes

Teleportation and the repair of dangling pages are not refinements. Without them the computation fails, in two different ways. Both show up on tiny graphs.

A dangling page leaks rank. In the left web, $X$ links to $Y$ and $Z$, $Y$ links to $Z$, and $Z$ links nowhere. Start the surfer uniformly and move the probability along the links, as the formula does with $d = 1$:

Probability that reaches $Z$ has nowhere to go, so it disappears. The five-page example leaks the same way through $E$, more slowly: following its links only, the total probability falls from 1 to $0.80$ after one step, $0.70$ after two, $0.28$ after ten and $0.024$ after thirty. The total shrinks by a factor approaching $0.885$ per step, a number that reappears below as an eigenvalue. Sending a dangling page's rank to every page stops the leak. With that repair the left web has PageRanks $(0.182, 0.273, 0.545)$ without teleportation and $(0.198, 0.282, 0.521)$ with it.

A spider trap absorbs rank. In the right web, $X$ and $Y$ link to each other, $Y$ also links to $Z$, and $Z$ and $W$ link only to each other. Nothing is dangling, so no rank leaks, but once probability enters $\{Z, W\}$ it never leaves:

The trap ends up with everything, and $X$ and $Y$, which link to each other and point a link into the trap, end with nothing (their combined share at step 20 is $0.0005$ and falling). Teleportation lets the surfer escape. With $d = 0.85$ the PageRanks are $(0.084, 0.109, 0.416, 0.391)$: the trap still holds $0.81$ of the rank, but $X$ and $Y$ keep a share. Teleportation limits what a trap can collect without removing its advantage, which is why link spammers build such structures (see Limits).

A web with two separate traps adds a third failure: the long-run answer depends on where the surfer starts, because a surfer who falls into one trap never sees the other. And two pages that link only to each other send a surfer who starts on the first to the second, then back, forever. Its distribution alternates between $(1, 0)$ and $(0, 1)$ and never settles. The matrix view below turns each failure into a statement about eigenvalues.

From links to the Google matrix

Number the pages $1$ to $N$ (here $A$ to $E$). The construction has three stages.

Stage 1: the link matrix $H$

The hyperlink matrix $H$ has one row for each page:

$$H_{qp} = \begin{cases} 1/L(q) & \text{if } q \text{ links to } p, \\ 0 & \text{otherwise.} \end{cases}$$

Row $q$ gives the probabilities of moving from page $q$ to each page by following a link. For the example, with rows and columns in the order $A, B, C, D, E$:

$$H = \begin{pmatrix} 0 & 1/2 & 1/2 & 0 & 0 \\ 0 & 0 & 1/2 & 0 & 1/2 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{pmatrix}.$$

If $\pi^{(k)}$ is a row vector giving the probability of the surfer being at each page after $k$ steps, then following one link turns it into $\pi^{(k)} H$: entry $p$ of the product is $\sum_q \pi^{(k)}_q H_{qp}$, the probability arriving at $p$ from every page that links to it. This is the formula of the previous section with $d = 1$ and no dangling term. The rows of $H$ sum to 1 except the last, which is all zeros because $E$ is dangling. That zero row is the leak: each step loses the probability that was at $E$.

Stage 2: the stochastic matrix $S$

Replace each zero row with the uniform row $(1/N, \dots, 1/N)$. With $a$ the column vector that has a 1 for each dangling page and 0 elsewhere, here $a = (0, 0, 0, 0, 1)^{\mathsf{T}}$,

$$S = H + \frac{1}{N} a \mathbf{1}^{\mathsf{T}} = \begin{pmatrix} 0 & 1/2 & 1/2 & 0 & 0 \\ 0 & 0 & 1/2 & 0 & 1/2 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 1/5 & 1/5 & 1/5 & 1/5 & 1/5 \end{pmatrix},$$

where $\mathbf{1}$ is the column vector of $N$ ones. Every entry of $S$ is nonnegative and every row sums to 1, which makes $S$ a (row-)stochastic matrix: each row is a probability distribution over the next page. Total probability is now conserved, since $\pi S \mathbf{1} = \pi \mathbf{1} = 1$.

Stage 3: the Google matrix $G$

Teleportation mixes $S$ with the matrix whose entries are all $1/N$:

$$G = dS + \frac{1 - d}{N} \mathbf{1}\mathbf{1}^{\mathsf{T}}.$$

With $d = 0.85$, every entry of $S$ is multiplied by $0.85$ and then increased by $0.15/5 = 0.03$. An entry of $1/2$ becomes $0.455$, an entry of $1$ becomes $0.88$, a zero becomes $0.03$, and the dangling row's $1/5$ becomes $0.17 + 0.03 = 0.2$:

$$G = \begin{pmatrix} 0.03 & 0.455 & 0.455 & 0.03 & 0.03 \\ 0.03 & 0.03 & 0.455 & 0.03 & 0.455 \\ 0.88 & 0.03 & 0.03 & 0.03 & 0.03 \\ 0.03 & 0.03 & 0.88 & 0.03 & 0.03 \\ 0.2 & 0.2 & 0.2 & 0.2 & 0.2 \end{pmatrix}.$$

Every row still sums to 1 (for the first, $0.03 \times 3 + 0.455 \times 2 = 1$), so $G$ is stochastic too, and now every entry is positive. One step of the full random surfer turns $\pi$ into $\pi G$. PageRank is the distribution that a step leaves unchanged:

$$\pi = \pi G, \qquad \sum_p \pi_p = 1.$$

Written out for one page, $\pi = \pi G$ is exactly the formula with the dangling term, and for the example it is the five equations solved above. In the language of linear algebra, $\pi$ is a left eigenvector of $G$ with eigenvalue 1, which is the same as an ordinary (right) eigenvector of $G^{\mathsf{T}}$. In the language of probability, $G$ describes a Markov chain and $\pi$ is its stationary distribution (Manning, Raghavan, and Schütze, 2008, §21.2). Some texts write $\alpha$ for the damping factor, and Haveliwala and Kamvar (2003) write $c$.

Why there is exactly one answer

The equation $\pi = \pi G$ asks for an eigenvector, and three things need showing: that the eigenvalue 1 exists, that there is an eigenvector for it with all entries positive, and that it is unique once scaled to sum to 1. A fourth, that power iteration reaches it from any start, is shown in How fast it converges. The arguments below use only the definition of an eigenvalue and the triangle inequality.

A stochastic matrix has eigenvalue 1

Because every row of $G$ sums to 1, multiplying $G$ by the all-ones column vector gives it back: $G\mathbf{1} = \mathbf{1}$. So $\mathbf{1}$ is a right eigenvector with eigenvalue 1. A matrix and its transpose have the same characteristic polynomial, $\det(\lambda I - G) = \det(\lambda I - G^{\mathsf{T}})$, so they have the same eigenvalues, and 1 is also an eigenvalue of $G^{\mathsf{T}}$. There is therefore some nonzero row vector $\pi$ with $\pi G = \pi$. The same holds for $S$, but not for $H$, whose zero row breaks $H\mathbf{1} = \mathbf{1}$.

No eigenvalue is larger than 1 in modulus. Suppose $Gx = \lambda x$ with $x \ne 0$, and let $i$ be an index where $\lvert x_i \rvert$ is largest. Row $i$ of the equation gives

$$\lvert \lambda \rvert\, \lvert x_i \rvert = \Big\lvert \sum_j G_{ij} x_j \Big\rvert \le \sum_j G_{ij} \lvert x_j \rvert \le \sum_j G_{ij} \lvert x_i \rvert = \lvert x_i \rvert,$$

using the triangle inequality, then $\lvert x_j \rvert \le \lvert x_i \rvert$, then the row sum. Dividing by $\lvert x_i \rvert$ gives $\lvert \lambda \rvert \le 1$. This argument uses only that the entries are nonnegative and the rows sum to 1, so it holds for $S$ as well.

With positive entries, the eigenvector is unique and positive

The Perron–Frobenius theorem states that a matrix with all entries positive has an eigenvalue of largest modulus that is real, positive, and simple, with an eigenvector whose entries are all positive. For a positive stochastic matrix such as $G$, the parts needed here follow in three short steps.

1. Only $\lambda = 1$ lies on the unit circle, and its right eigenvectors are constant. If $\lvert \lambda \rvert = 1$ in the chain of inequalities above, both inequalities must be equalities. The second is an equality only if $\lvert x_j \rvert = \lvert x_i \rvert$ for every $j$, because every $G_{ij}$ is positive and so every term counts. The first is an equality only if all the numbers $G_{ij} x_j$ point in the same direction in the complex plane. Equal moduli and equal directions mean all $x_j$ are equal, so $x$ is a multiple of $\mathbf{1}$, and then $Gx = x$ gives $\lambda = 1$.
2. The left eigenvector is unique up to scale. Step 1 shows that the solutions of $(G - I)x = 0$ form a one-dimensional space, so $G - I$ has rank $N - 1$. A matrix and its transpose have the same rank, so the solutions of $\pi (G - I) = 0$ also form a one-dimensional space. Every left eigenvector for eigenvalue 1 is a multiple of one vector, and requiring the entries to sum to 1 picks out one.
3. That vector can be taken positive. Let $\pi G = \pi$. For each page $p$, $\lvert \pi_p \rvert = \lvert \sum_q \pi_q G_{qp} \rvert \le \sum_q \lvert \pi_q \rvert G_{qp}$. Summing over $p$, the left side gives $\sum_p \lvert \pi_p \rvert$ and the right side gives $\sum_q \lvert \pi_q \rvert \sum_p G_{qp} = \sum_q \lvert \pi_q \rvert$, the same total. So every one of the inequalities is an equality, which with all $G_{qp} > 0$ means the nonzero $\pi_q$ all have the same sign. Choose it positive. Then $\pi_p = \sum_q \pi_q G_{qp}$ is a sum of nonnegative terms with at least one positive, so every $\pi_p > 0$.

The argument needed every entry of $G$ to be positive. Teleportation guarantees this, since every entry is at least $(1 - d)/N > 0$: from any page the surfer can reach any other page in a single step. Without it, each failure from the tiny webs breaks one of the steps:

• Pages can be unreachable. Following links in $H$, nothing ever arrives at $D$, so a surfer who only follows links visits $D$ at most once, and its long-run share is 0. The positivity in step 3 fails.
• Rank can be trapped. If the graph contains two traps, there are infinitely many stationary distributions, one for each way of dividing the probability between them, and step 2 fails. In the language of Markov chains, such a chain has two irreducible closed subsets: sets of states that the chain never leaves and that contain no smaller such set. The multiplicity of the eigenvalue 1 of a stochastic matrix equals the number of them (Haveliwala and Kamvar, 2003, Theorem 3 in their appendix, quoting Isaacson and Madsen).
• The walk can oscillate. For the two pages that only link to each other, the link matrix has eigenvalues $1$ and $-1$. The eigenvalue $-1$ is on the unit circle, step 1 fails, and the part of the distribution along its eigenvector flips sign every step and never decays.

In Markov chain terms, $G$ is irreducible, since every page can reach every other, and aperiodic, since the walk does not cycle with a fixed period, and such a chain has a unique stationary distribution that it approaches from any start.

The five-page example is, by luck, well behaved even without teleportation. The dangling repair gives $E$ a link to every page, including itself, and every page can reach $E$ (through $B$), so $S$ is irreducible, and the self-step makes it aperiodic. That is why the column "without teleportation" above has a unique answer. A web with a spider trap, which the dangling repair does not touch, has no such luck.

The eigenvalues of the example

The characteristic polynomial of $S$, computed in exact fractions, factors as

$$\det(\lambda I - S) = (\lambda - 1)\left(\lambda^4 + \tfrac{4}{5}\lambda^3 + \tfrac{1}{5}\lambda^2 + \tfrac{1}{20}\right).$$

The factor $\lambda - 1$ is the eigenvalue every stochastic matrix has. The quartic has two complex-conjugate pairs of roots. Rounded to four decimals, the eigenvalues of the three matrices are:

The largest eigenvalue of $H$ is $0.8846$, the real root of $\lambda^3 - \lambda/2 - 1/4$, and it is less than 1 because $H$ loses probability at $E$. This is the factor by which the total probability shrank per step in the leak described earlier. Repairing the dangling row lifts the top eigenvalue to exactly 1. Every other eigenvalue of $S$ lies strictly inside the unit circle, as expected for an irreducible, aperiodic chain.

Comparing the rows for $S$ and $G$ shows the pattern: apart from the eigenvalue 1, each eigenvalue of $G$ is exactly $0.85$ times an eigenvalue of $S$. For instance $0.85 \times (-0.5542 + 0.3417i) = -0.4711 + 0.2904i$, and $0.85 \times 0.6511 = 0.5534$.

Why every other eigenvalue shrinks by $d$

The pattern holds for every graph. Let $v$ be the teleportation distribution, a column vector of nonnegative entries summing to 1 (uniform, $v = \mathbf{1}/N$, so far), so that $G = dS + (1-d)\mathbf{1}v^{\mathsf{T}}$. Choose any invertible matrix $Q$ whose first column is $\mathbf{1}$, and write $Q = (\mathbf{1} \mid X)$.

1. Since $S\mathbf{1} = \mathbf{1}$, the first column of $Q^{-1} S Q$ is $Q^{-1}\mathbf{1}$, which is the first unit vector $e_1$ (because $Q e_1 = \mathbf{1}$). So $Q^{-1} S Q$ is block upper triangular, $\begin{pmatrix} 1 & b^{\mathsf{T}} \\ 0 & T \end{pmatrix}$ for some row $b^{\mathsf{T}}$ and $(N-1) \times (N-1)$ block $T$. Its eigenvalues, which are those of $S$, are 1 together with the eigenvalues $\lambda_2, \dots, \lambda_N$ of $T$.
2. For the teleportation term, $Q^{-1}\mathbf{1}v^{\mathsf{T}}Q = e_1 (v^{\mathsf{T}}Q) = e_1 (v^{\mathsf{T}}\mathbf{1},\ v^{\mathsf{T}}X) = \begin{pmatrix} 1 & v^{\mathsf{T}}X \\ 0 & 0 \end{pmatrix}$, using $v^{\mathsf{T}}\mathbf{1} = 1$. All of it sits in the first row.
3. Adding the two with weights $d$ and $1-d$, $$Q^{-1} G Q = \begin{pmatrix} 1 & d\,b^{\mathsf{T}} + (1-d)\,v^{\mathsf{T}}X \\ 0 & d\,T \end{pmatrix}.$$ The eigenvalues of $G$ are therefore 1 and $d\lambda_2, \dots, d\lambda_N$.

Since $S$ is stochastic, every $\lvert \lambda_i \rvert \le 1$, so every eigenvalue of $G$ other than the first has modulus at most $d$. Haveliwala and Kamvar (2003, Theorem 1) proved this bound, $\lvert \lambda_2(G) \rvert \le d$, for any stochastic $S$ and any teleportation distribution, by a different argument. They also proved (Theorem 2) that equality holds whenever the chain of $S$ has at least two irreducible closed subsets. The derivation above shows why: two such subsets make the eigenvalue 1 of $S$ appear twice, once in $T$, and $d$ times it is $d$. They point out that the web graph contains many such subsets, so on the real web $\lvert \lambda_2 \rvert = d$ exactly. The second panel of the convergence figure below is a small web where this happens.

The eigenvector, normalized

A numerical eigenvalue routine (numpy's eig applied to $G^{\mathsf{T}}$) returns the eigenvector for eigenvalue 1 scaled to unit Euclidean length:

$$x = (0.6308,\ 0.3724,\ 0.6194,\ 0.1043,\ 0.2626).$$

Any multiple of $x$ is an equally valid eigenvector, and a routine may as easily return $-x$. Dividing by the sum of the entries, $1.9895$, gives the probability vector

$$\pi = (0.3171,\ 0.1872,\ 0.3113,\ 0.0524,\ 0.1320),$$

the PageRank of the table above. Dividing $x$ by its fourth entry instead gives $(6.046, 3.570, 5.937, 1, 2.517)$, the vector in units of $t$ found by hand. The hand solution, the eigenvector routine and power iteration are three routes to the same vector.

Power iteration

For a matrix with billions of rows, solving the equations directly is out of the question. Power iteration applies the walk repeatedly instead: start from the uniform distribution $\pi^{(0)} = (1/N, \dots, 1/N)$ and compute $\pi^{(k+1)} = \pi^{(k)} G$ until the values stop changing. For the example, with the last column the $L_1$ distance $\lVert \pi^{(k)} - \pi \rVert_1 = \sum_p \lvert \pi^{(k)}_p - \pi_p \rvert$ to the final answer:

The first step can be checked by hand from $G$. Starting from $0.2$ everywhere, page $C$ receives $0.2 \times (0.455 + 0.455 + 0.03 + 0.88 + 0.2) = 0.404$, the sum of column $C$ of $G$ times $0.2$. $D$ receives $0.2 \times (0.03 \times 4 + 0.2) = 0.064$.

The early iterations swing back and forth as PageRank flows around the cycle from $A$ to $C$ and back. After step 1, $C$ holds $0.404$, collected from three in-links. At step 2 it passes almost all of that to $A$, which jumps to $0.399$ while $C$ falls. With the stopping rule that the total change in the five values falls below $10^{-10}$, the computation ended after 40 iterations.

$G$ is never formed in practice. It is dense, with $N^2$ entries, while $H$ is sparse, with one entry for each link. Because the dangling repair and the teleportation term each add the same amount to every page, each iteration can be computed from $H$ alone:

$$\pi^{(k+1)} = d\, \pi^{(k)} H + \frac{d\,\pi^{(k)} a + 1 - d}{N} \mathbf{1}^{\mathsf{T}},$$

where $\pi^{(k)} a$ is the total probability currently on dangling pages. This costs time proportional to the number of links. The computation runs over the link graph that a connectivity server stores, and it is done offline. PageRank does not depend on the query, so it is computed once for the collection and stored with each page.

How fast it converges

A short calculation shows that power iteration always converges and bounds how fast. Subtract $\pi = \pi G$ from $\pi^{(k+1)} = \pi^{(k)} G$ and expand $G$:

$$\pi^{(k+1)} - \pi = d\,(\pi^{(k)} - \pi)\,S + \frac{1-d}{N}\,\big((\pi^{(k)} - \pi)\mathbf{1}\big)\,\mathbf{1}^{\mathsf{T}}.$$

Both vectors sum to 1, so $(\pi^{(k)} - \pi)\mathbf{1} = 0$ and the teleportation term vanishes. Multiplying a row vector $e$ by a stochastic matrix cannot increase its $L_1$ norm, since $\sum_p \lvert \sum_q e_q S_{qp} \rvert \le \sum_q \lvert e_q \rvert \sum_p S_{qp} = \sum_q \lvert e_q \rvert$. Therefore

$$\lVert \pi^{(k+1)} - \pi \rVert_1 \le d\, \lVert \pi^{(k)} - \pi \rVert_1, \qquad \lVert \pi^{(k)} - \pi \rVert_1 \le d^k\, \lVert \pi^{(0)} - \pi \rVert_1.$$

The error shrinks by at least the factor $d$ at every step, from any starting distribution and on any graph. This also proves that the iteration converges to $\pi$ from every start, the fourth property promised above. With $d = 0.85$, reducing the error by a factor of $10^{10}$ takes at most $\ln 10^{-10} / \ln 0.85 \approx 142$ iterations, however large the web.

The bound is a guarantee, not a prediction. Over many steps the error shrinks in proportion to $\lvert \lambda_2 \rvert^k$, where $\lambda_2$ is the eigenvalue of $G$ with the second-largest modulus: write $\pi^{(0)}$ in terms of the eigenvectors of $G$, and each step multiplies the component along eigenvector $i$ by $\lambda_i$, so every component but the first fades and the slowest-fading one sets the pace. For the example $\lvert \lambda_2 \rvert = 0.85 \times 0.6511 = 0.5534$, and a reduction by $10^{10}$ needs about $\ln 10^{-10} / \ln 0.5534 \approx 39$ iterations, close to the 40 observed. $\lambda_2$ is complex, and complex eigenvalues make the error rotate as it shrinks, which appears as values that overshoot and come back. The rotation also makes the error fall unevenly: in the table, the ratio of successive errors varies between $0.39$ and $0.73$ in the first eight steps, while its long-run geometric average is $0.5534$.

Real web graphs are like the right panel, since they contain many traps, so the asymptotic rate of PageRank's convergence on the web is $d$ exactly, independent of the size of the graph (Haveliwala and Kamvar, 2003). On the two-trap web, $S$ has eigenvalues $1, 1, -1, -1, 0$, and $G$ has $1, d, -d, -d, 0$.

The bound also shows the cost of a damping factor close to 1. Raising $d$ gives the link structure more weight relative to teleportation, but it slows convergence, and it makes the result more sensitive to small changes in the graph and to groups of pages that trap rank (Langville and Meyer, 2006). Haveliwala and Kamvar (2003) connect the second point to the eigenvalues as well: the gap between 1 and $\lvert \lambda_2 \rvert$ governs how stable the stationary distribution is under perturbation of the chain.

The random surfer as a Markov chain

The algebra and the thought experiment describe the same object. $G_{qp}$ is the probability that a surfer on page $q$ is on page $p$ one step later. By the rules of probability, the entries of $G^k$ are the probabilities of going from $q$ to $p$ in exactly $k$ steps, and a surfer whose position is uncertain, with distribution $\pi^{(0)}$, has distribution $\pi^{(0)} G^k$ after $k$ steps. Power iteration is literally the evolution of the surfer's probability distribution, one click at a time.

Because power iteration converges to $\pi$ from every start, every row of $G^k$ approaches $\pi$: where the surfer started stops mattering. In the example, row $D$ of $G$ is $(0.03, 0.03, 0.88, 0.03, 0.03)$, since a surfer on $D$ almost certainly moves to $C$. Row $D$ of $G^2$ is $(0.783, 0.048, 0.086, 0.035, 0.048)$, since from $C$ the surfer almost certainly moves on to $A$. By $G^{10}$ row $D$ is $(0.315, 0.190, 0.312, 0.053, 0.130)$, and the largest difference between any entry of $G^k$ and the corresponding entry of $\pi$ is $0.57$ for $k = 1$, $0.046$ for $k = 5$, $0.0029$ for $k = 10$, and $9 \times 10^{-6}$ for $k = 20$.

The definition at the start of this article was the long-run fraction of time spent on a page, not a probability at one moment. The ergodic theorem for Markov chains says that for an irreducible chain the two agree: the fraction of the first $n$ steps that a single surfer spends on page $p$ converges to $\pi_p$ as $n$ grows. This can be checked by simulation. A surfer following the rules for 100,000 steps on the example, repeated 30 times with different random seeds, spent the following fractions of its time on each page (median over the 30 runs, with the interquartile range):

The simulated surfer agrees with the eigenvector to within the run-to-run variation. Simulation is a poor way to compute PageRank, since its error falls only as the inverse square root of the number of steps, but it confirms that the eigenvector means what the thought experiment says.

PageRank as a linear system

Because $\pi$ sums to 1, the teleportation term $\pi \frac{1-d}{N} \mathbf{1}\mathbf{1}^{\mathsf{T}}$ equals $\frac{1-d}{N}\mathbf{1}^{\mathsf{T}}$, and the eigenvector equation becomes a linear system:

$$\pi (I - dS) = \frac{1 - d}{N} \mathbf{1}^{\mathsf{T}}.$$

The matrix $I - dS$ is always invertible, since every eigenvalue of $dS$ has modulus at most $d < 1$, so $I - dS$ cannot have eigenvalue 0. Solving the system for the example gives the same values as power iteration, and solving it in exact rational arithmetic gives $\pi_A = 1877600/5921921$, with the same denominator for the other four. For a small graph this is the simplest way to compute PageRank exactly. The five equations solved by hand at the start are this system written out.

The system can also be written with the sparse $H$ in place of $S$. Solving $x (I - dH) = \frac{1}{N}\mathbf{1}^{\mathsf{T}}$ and dividing $x$ by the sum of its entries gives the same $\pi$, because the dangling term only adds a multiple of $\mathbf{1}^{\mathsf{T}}$ to the right-hand side, which the final normalization absorbs.

Expanding the inverse as a series, $(I - dS)^{-1} = I + dS + d^2S^2 + \cdots$, gives an interpretation:

$$\pi = \frac{1 - d}{N} \sum_{k=0}^{\infty} d^k\, \mathbf{1}^{\mathsf{T}} S^k.$$

The surfer lands on a random page, then follows $k$ links before the next jump, with probability $(1-d)d^k$. A page's PageRank adds up all the paths that end at it, with paths of length $k$ discounted by $d^k$. Long chains of links count, but less than short ones. Power iteration computes this sum one term at a time.

Personalized PageRank

Nothing requires the surfer to teleport uniformly, and Page, Brin, Motwani, and Winograd (1999) already proposed biasing the jump. Replacing the uniform jump with a probability vector $v$ over pages, and sending the surfer from a dangling page according to $v$ as well, gives

$$G_v = d\,(H + a v^{\mathsf{T}}) + (1 - d)\, \mathbf{1} v^{\mathsf{T}}, \qquad \pi \propto v^{\mathsf{T}} (I - dH)^{-1}.$$

The second form follows as in the previous section: $\pi = \pi G_v$ gives $\pi (I - dH) = (d\,\pi a + 1 - d)\, v^{\mathsf{T}}$, a scalar times $v^{\mathsf{T}}$, and normalizing removes the scalar. The surfer now always restarts from pages favored by $v$, and PageRank measures importance as seen from those pages. In the example, teleporting only to $A$ gives $(0.452, 0.192, 0.274, 0, 0.082)$. $A$ rises, and $D$, which no path from $A$ reaches, falls to zero. Teleporting only to $D$ gives $(0.290, 0.123, 0.341, 0.194, 0.052)$. $D$ holds more than the $1 - d = 0.15$ that the jumps deliver to it, because the surfer who reaches the dangling page $E$ is also sent back to $D$. Some implementations keep the uniform jump for dangling pages while personalizing the rest, which gives slightly different numbers.

Haveliwala (2002) used this to compute topic-sensitive PageRank: a separate PageRank vector for each of a set of broad topics, each teleporting only to pages known to belong to its topic, combined at query time according to how well the query matches each topic. With $v$ concentrated on a single page, personalized PageRank measures how closely every other page is connected to that one, and it is widely used for recommendation and for finding related pages. The eigenvalue analysis above holds for any $v$ (with $H + a v^{\mathsf{T}}$ in the role of $S$), so the convergence bound $d^k$ applies to personalized PageRank too.

HITS

Kleinberg (1999) proposed a related method, HITS (hyperlink-induced topic search), which gives each page two scores. A good authority is linked to by many good hubs, and a good hub links to many good authorities. With $M$ the adjacency matrix of the graph, $M_{qp} = 1$ if $q$ links to $p$ (the letter $A$ already names a page here), the authority scores $x$ and hub scores $y$ satisfy

$$x \propto M^{\mathsf{T}} y, \qquad y \propto M x.$$

Alternating the two updates, and rescaling after each, converges to the principal eigenvectors of $M^{\mathsf{T}}M$ for the authorities and $MM^{\mathsf{T}}$ for the hubs. There is no teleportation and no damping factor.

On the five-page example, the authority scores, scaled to sum to 1, converge to $1/\sqrt{3} \approx 0.577$ for $C$, $(3 - \sqrt{3})/6 \approx 0.211$ each for $B$ and $E$, and 0 for $A$ and $D$. The hub scores are $(\sqrt{3} - 1)/2 \approx 0.366$ each for $A$ and $B$, $2 - \sqrt{3} \approx 0.268$ for $D$, and 0 for $C$ and $E$. $C$ is the authority, linked from three hubs. $A$, which PageRank placed first, gets no authority at all. Its only in-link comes from $C$, and $C$ links to nothing else, so no page that links to $A$ also links to $B$, $C$ or $E$. In $M^{\mathsf{T}}M$, whose $(p, p')$ entry counts the pages linking to both $p$ and $p'$, page $A$ forms a separate block with eigenvalue 1, while the block for $B$, $C$ and $E$,

$$\begin{pmatrix} 1 & 1 & 0 \\ 1 & 3 & 1 \\ 0 & 1 & 1 \end{pmatrix},$$

has eigenvalues $2 + \sqrt{3} \approx 3.73$, $1$ and $2 - \sqrt{3}$. The principal eigenvector, proportional to $(1, 1 + \sqrt{3}, 1)$ on that block, lies entirely in the larger block. This tendency to settle on the most densely connected community and give zero to the rest is a known property of HITS.

HITS was designed to run on a small subgraph around the results of a query, so its scores are query-dependent, which makes them more specific to the topic than PageRank's but requires computation at query time (Manning, Raghavan, and Schütze, 2008, §21.3).

Limits

PageRank measures popularity among link authors, which is not the same as relevance or quality. It is computed without regard to the query, so it can only reorder pages that text matching has already found. Its value also drew manipulation. Link farms, networks of pages that link to each other and to a target, and purchased links inflate a page's PageRank. The spider-trap example shows the mechanism: a closed group of pages kept $0.81$ of the rank in a four-page web even with teleportation. Haveliwala and Kamvar (2003) observe that each pair of such closed structures gives $G$ an eigenvector with eigenvalue $d$, and suggest that these eigenvectors may help in detecting link spam. Search engines introduced the rel="nofollow" link attribute in 2005, so that links in comments and advertisements could be excluded, and developed methods to detect link spam. In modern web search, PageRank is one of many signals, combined with text matching, anchor text, user behavior, and others in learned ranking functions.

Every number in this article is computed by tools/experiments/crawling/pagerank_math.py in the site repository, and the figures by tools/figures/pagerank.py.

References

• Brin, S., and Page, L. (1998). The anatomy of a large-scale hypertextual Web search engine. Computer Networks and ISDN Systems, 30(1–7), 107–117.
• Haveliwala, T. H. (2002). Topic-sensitive PageRank. In Proceedings of WWW 2002, 517–526.
• Haveliwala, T. H., and Kamvar, S. D. (2003). The second eigenvalue of the Google matrix. Technical report, Stanford University.
• Kleinberg, J. M. (1999). Authoritative sources in a hyperlinked environment. Journal of the ACM, 46(5), 604–632.
• Langville, A. N., and Meyer, C. D. (2006). Google's PageRank and Beyond: The Science of Search Engine Rankings. Princeton University Press.
• Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to Information Retrieval, chapter 21. Cambridge University Press.
• Page, L., Brin, S., Motwani, R., and Winograd, T. (1999). The PageRank citation ranking: Bringing order to the Web. Technical report, Stanford InfoLab.