A hyperlink is a small act of endorsement: when a page links to another, it is, in some sense, vouching for it. PageRank turns this observation into a precise linear-algebra problem. It models the entire web as a directed graph and asks for a single number per page, its rank, such that a page's rank is high exactly when it is linked to by other high-ranking pages. This is a genuinely recursive definition — a page's importance depends on the importance of the pages linking to it, which in turn depends on the importance of their linkers, and so on — and turning it into something computable is a nice illustration of how far eigenvectors and the spectral theory of graphs can carry a seemingly circular idea.
The Web as a Directed Graph
Model the web as a directed graph \(G=(V,E)\) with \(n=|V|\) pages \(P_1,\ldots,P_n\). A directed edge \((i,j)\in E\) means that \(P_i\) contains a hyperlink to \(P_j\). Write \(C(i)\) for the out-degree of \(P_i\), the number of distinct pages it links to,
\[C(i)=|\{j : (i,j)\in E\}|.\]
The graph is stored as a link matrix \(\mathbf{L}\in\{0,1\}^{n\times n}\) with \(l_{ij}=1\) if \((i,j)\in E\) and \(l_{ij}=0\) otherwise. Unlike the adjacency matrices used for undirected graphs, \(\mathbf{L}\) is not symmetric in general: a link from \(P_i\) to \(P_j\) says nothing about whether \(P_j\) links back.
A Recursive Definition of Importance
The founding idea, due to Brin and Page (1998), is that a page distributes its own importance equally among every page it links to, and a page's rank is the sum of the shares it receives this way,
\[\operatorname{PR}(P_j)=\sum_{i\,:\,(i,j)\in E}\frac{\operatorname{PR}(P_i)}{C(i)}.\]
A page linked to by few, important pages can outrank a page linked to by many unimportant ones, since each incoming link is weighted by how much rank its source has to give away, divided by how many other places it is splitting that rank between.
To make this computable, normalize \(\mathbf{L}\) row by row into a transition matrix \(\mathbf{H}\),
\[h_{ij}=\begin{cases}\dfrac{1}{C(i)} & \text{if } (i,j)\in E\\[4pt] 0 & \text{otherwise,}\end{cases}\]
Whenever every \(C(i)>0\), each row of \(\mathbf{H}\) sums to one, so \(\mathbf{H}\) is row-stochastic and has a natural probabilistic reading: \(h_{ij}\) is the probability that a surfer standing on \(P_i\) and clicking a uniformly random outgoing link ends up on \(P_j\). This turns the whole problem into a Markov chain with state space \(\{P_1,\ldots,P_n\}\) and one-step transition probabilities given by \(\mathbf{H}\): if \(\pi_n(i)\) denotes the probability that the surfer is on page \(P_i\) after \(n\) clicks, one further click gives
\[\pi_{n+1}(j)=\sum_{i=1}^n\pi_n(i)\,h_{ij},\]
a page's next-step probability is the sum, over every page linking to it, of that page's current probability weighted by the chance a surfer there clicks through. Collecting the \(\pi_n(i)\) into a row vector \(\boldsymbol{\pi}_n=(\pi_n(1),\ldots,\pi_n(n))\), this is exactly the matrix-vector product
\[\boldsymbol{\pi}_{n+1}=\boldsymbol{\pi}_n\mathbf{H},\]
since the \(j\)-th entry of \(\boldsymbol{\pi}_n\mathbf{H}\) is \(\sum_i\pi_n(i)h_{ij}\), precisely the sum above. Repeating this step traces out the whole history of the walk, \(\boldsymbol{\pi}_0,\boldsymbol{\pi}_1, \boldsymbol{\pi}_2,\ldots\), and the founding recursive definition of PageRank asks for a distribution that this history eventually settles on: a stationary distribution, meaning a probability vector \(\boldsymbol{\pi}\) left completely unchanged by one further step of the walk,
\[\boldsymbol{\pi}=\boldsymbol{\pi}\mathbf{H}.\]
This says \(\boldsymbol{\pi}\) is a left eigenvector of \(\mathbf{H}\) for eigenvalue \(1\) — equivalently, a right eigenvector of \(\mathbf{H}^T\) for eigenvalue \(1\), in the same sense discussed for general eigenvectors earlier. \(\operatorname{PR}(P_j)=\pi(j)\) is then the long-run fraction of clicks that land on \(P_j\), regardless of where the surfer started.
A Markov Chain Simulator
The equation \(\boldsymbol{\pi}=\boldsymbol{\pi}\mathbf{H}\) is easiest to trust after watching it happen. Every simulation on this page is powered by a small reusable MarkovGraph helper that wraps a transition matrix and knows how to take a single step of the walk, repeatedly apply that step (the brute-force route to a stationary distribution used further down), and solve for the stationary distribution directly as a linear system.
On a small four-page graph, page \(0\) links to pages \(1\) and \(2\), page \(1\) links only to page \(2\), page \(2\) links only to page \(3\), and page \(3\) links back to both \(0\) and \(2\),
\[\mathbf{H}=\begin{pmatrix}0 & 1/2 & 1/2 & 0\\0&0&1&0\\0&0&0&1\\ 1/2&0&1/2&0\end{pmatrix}.\]
Each dot below is an independent random surfer starting on a random page and repeatedly jumping to a next page chosen according to the row of \(\mathbf{H}\) for its current page; the live numbers next to each page track what fraction of the \(33\) surfers are on it right now.
The same convergence shows up directly in the numbers, not just in the animation: starting every page at \(\pi_0(i)=0.25\) and repeatedly applying \(\boldsymbol{\pi}_{k+1}=\boldsymbol{\pi}_k\mathbf{H}\) on this exact graph traces out
Two Ways the Naive Equation Breaks
Two structural problems keep \(\boldsymbol{\pi}=\boldsymbol{\pi}\mathbf{H}\) from being solvable in general, and both are easiest to see on small examples.
Dangling nodes
A page with no outgoing links at all (\(C(i)=0\)) gives a row of \(\mathbf{H}\) that is entirely zero, so \(\mathbf{H}\) is no longer row-stochastic. In the random-surfer picture, a surfer who lands on such a dangling node has nowhere left to click and simply vanishes from the system: iterating \(\boldsymbol{\pi}_{k+1}=\boldsymbol{\pi}_k\mathbf{H}\) starting from a uniform guess on a four-page site with one dangling page produces the totals
\[1,\ 0.7875,\ 0.6653,\ 0.5883,\ 0.5017,\ 0.4413,\ldots\]
steadily leaking toward zero instead of settling on a meaningful distribution.
Reducible graphs
Even when every page has outgoing links, \(\boldsymbol{\pi}=\boldsymbol{\pi}\mathbf{H}\) can fail to have a unique solution. A Markov chain is called reducible when its state space splits into two or more classes such that, once the walk enters one class, it can never reach any state outside that class again; a chain that is not reducible, one in which every state is reachable from every other, is called irreducible. Take two completely separate two-page loops, \(X\leftrightarrow Y\) and \(Z\leftrightarrow W\), with no links between the two pairs, as drawn below: there is no sequence of clicks that ever gets a surfer from \(\{X,Y\}\) to \(\{Z,W\}\) or back.
Both
\[\boldsymbol{\pi}_1=(0.5,\,0.5,\,0,\,0)\qquad\text{and}\qquad\boldsymbol{\pi}_2=(0,\,0,\,0.5,\,0.5)\]
satisfy \(\boldsymbol{\pi}=\boldsymbol{\pi}\mathbf{H}\), and so does every convex combination of the two: \(\mathbf{H}\) has eigenvalue \(1\) with multiplicity two, one for each disconnected component, so the stationary distribution depends on which component the walk started in and is not unique. This is exactly the failure mode the Perron–Frobenius theorem warns about: without irreducibility the dominant eigenvector need not be unique.
Periodic graphs
A two-page loop is also periodic: the surfer returns to its starting page only every even number of clicks, never on an odd one, so the walk visits states in a rigid, repeating pattern instead of settling down. Algebraically, its transition matrix has eigenvalue \(-1\), tied in magnitude with the dominant eigenvalue \(1\). Starting the surfer concentrated on \(X\) with distribution \((0.7,0.1,0.1,0.1)\), repeatedly applying \(\mathbf{H}\) never converges at all; it alternates forever between \((0.7,0.1,0.1,0.1)\) and \((0.1,0.7,0.1,0.1)\), while the untouched \(Z,W\) pair sits still at \((0.1,0.1)\) throughout, as the plot below shows:
Without aperiodicity, power iteration need not converge at all, even when a unique stationary distribution technically exists. A classical fix for periodicity alone is to make the walk lazy, staying put with probability \(1/2\) on every step instead of always moving, \(\boldsymbol{\pi}_{k+1}=\boldsymbol{\pi}_k\cdot \tfrac12(\mathbf{H}+\mathbf{I})\); averaging \(\mathbf{H}\) with the identity shifts every eigenvalue \(\lambda\) to \((1+\lambda)/2\), which moves the disruptive eigenvalue \(-1\) to \(0\) and does make the two-loop example converge. But laziness leaves the eigenvalue-\(1\) multiplicity untouched, so it cures periodicity without curing reducibility: the two loops still never mix, and the limit still depends on which loop the walk started in. Only teleportation, which makes every page reachable from every other in a single step, fixes both problems together.
The Random Surfer and the Damping Factor
Both problems are fixed by the same device: give the surfer a way to leave the current page that does not depend on the link structure at all. First, patch every dangling row of \(\mathbf{H}\) to redistribute uniformly instead of vanishing,
\[\tilde h_{ij}=\begin{cases}h_{ij} & \text{if } C(i)>0\\[2pt] 1/n & \text{if } C(i)=0,\end{cases}\]
modeling a surfer stuck at a dead end who simply jumps to a uniformly random page instead of stopping. Then introduce a damping factor \(d\in(0,1)\) (Brin and Page use \(d=0.85\)): with probability \(d\) the surfer follows a random link as before, and with the remaining probability \(1-d\) they get bored and teleport to a uniformly random page, regardless of where they currently are. Writing \(\mathbf{J}\) for the \(n\times n\) all-ones matrix, this defines the Google matrix
\[\mathbf{M}=d\,\tilde{\mathbf{H}}+\frac{1-d}{n}\mathbf{J},\]
and the defining equation of PageRank becomes \(\boldsymbol{\pi}=\boldsymbol{\pi}\mathbf{M}\), or, written out per page (only counting genuine, non-dangling incoming links in the sum),
\[\operatorname{PR}(P_j)=\frac{1-d}{n}+d\sum_{i\,:\,(i,j)\in E,\,C(i)>0}\frac{\operatorname{PR}(P_i)}{C(i)}.\]
Normalizing \(\boldsymbol{\pi}\) to sum to \(n\) instead of \(1\) (multiply both sides by \(n\)) recovers the form in which the original formula is often quoted, \(\operatorname{PR}(P_j)=(1-d)+d\sum\operatorname{PR}(P_i)/C(i)\); the two conventions differ only by this constant scale factor and rank pages identically.
Why Damping Guarantees a Unique Answer
Every entry of \(\mathbf{M}\) is at least \((1-d)/n>0\), so \(\mathbf{M}\) is strictly positive regardless of how the underlying link graph looks. A strictly positive matrix is automatically irreducible and aperiodic (in Markov-chain terms, it is primitive), so the Perron–Frobenius theorem applies unconditionally: \(\mathbf{M}\) has a simple dominant eigenvalue equal to \(1\) (row-stochastic matrices always have a spectral radius of exactly \(1\)) with a strictly positive eigenvector, unique up to scale. Damping does not just patch dangling nodes; it also cures reducibility and periodicity outright. Revisiting the disconnected two-loop example with \(d=0.85\), the Google matrix has eigenvalues
\[1,\ 0.85,\ -0.85,\ -0.85,\]
so the dominant eigenvalue \(1\) is now simple and strictly larger in magnitude than every other eigenvalue. Power iteration converges from any starting point, and starting concentrated on \(X\) or on \(W\) both settle on the same uniform vector \((0.25,0.25,0.25,0.25)\), exactly as the theorem predicts.
Damping matters most when the link structure is genuinely directed and asymmetric. On an undirected graph (every link reciprocated), the plain, undamped walk already has a unique stationary distribution whenever the graph is connected and not bipartite, and that distribution depends only on degree, never on the finer link topology: \(\pi_i=d_i/(2|E|)\), where \(d_i\) is the degree of vertex \(i\). Grolmusz (2015) shows that damped PageRank on an undirected graph equals this degree distribution exactly if and only if the graph is regular, and otherwise stays much closer to it than to the uniform distribution, which is exactly what a direct computation confirms on a small irregular example. This is why PageRank is genuinely informative mainly for directed graphs like the web, where an incoming link is not automatically reciprocated by an outgoing one; on an undirected graph it mostly just rediscovers degree centrality.
A Complete Worked Example
Consider a four-page site: Home links to Blog and About; Blog links back to Home and out to Contact; About links back to Home; and Contact has no outgoing links at all — the kind of small directed graph you can sketch and export to TikZ yourself with the graph editor.
The out-degrees are \(C(\text{Home})=2\), \(C(\text{Blog})=2\), \(C(\text{About})=1\), \(C(\text{Contact})=0\). After fixing the dangling Contact row to \(1/4\) everywhere and applying the damping factor \(d=0.85\), solving \(\boldsymbol{\pi}=\boldsymbol{\pi}\mathbf{M}\) with \(\sum\pi_i=1\) gives
\[\operatorname{PR}(\text{Home})=0.3676,\quad \operatorname{PR}(\text{Blog})=\operatorname{PR}(\text{About})=0.2303,\quad \operatorname{PR}(\text{Contact})=0.1719,\]
or, on the classical sum-to-\(n\) scale, \(1.4704\), \(0.9210\), \(0.9210\), and \(0.6875\) respectively. Blog and About receive exactly the same rank even though Blog additionally links onward to Contact and About does not: PageRank depends only on a page's incoming links, never on what it chooses to do with its own outgoing ones. Starting the power iteration from the uniform guess \((0.25,0.25,0.25,0.25)\) and repeatedly multiplying by \(\mathbf{M}\) gives
| Step | Home | Blog | About | Contact |
|---|---|---|---|---|
| 0 | 0.2500 | 0.2500 | 0.2500 | 0.2500 |
| 1 | 0.4094 | 0.1969 | 0.1969 | 0.1969 |
| 2 | 0.3304 | 0.2533 | 0.2533 | 0.1630 |
| 3 | 0.3951 | 0.2125 | 0.2125 | 0.1798 |
| 4 | 0.3467 | 0.2436 | 0.2436 | 0.1660 |
| … | … | … | … | … |
| \(\infty\) | 0.3676 | 0.2303 | 0.2303 | 0.1719 |
slowly spiraling in on the exact answer, exactly the behavior described for power iteration in general, as the plot below makes visible: each page's estimate oscillates with shrinking amplitude around its true value instead of approaching it monotonically.
Three Equivalent Ways to Compute PageRank
Because \(\mathbf{M}\) is a strictly positive matrix with dominant eigenvalue \(1\), \(\boldsymbol{\pi}\) can be found by any of the standard routes to a dominant eigenvector, and all three agree exactly on the worked example above:
- Brute force (power iteration). Repeatedly apply \(\boldsymbol{\pi}_{k+1}=\boldsymbol{\pi}_k\mathbf{M}\) from any starting distribution, exactly the \(\texttt{bruteForce}\) method of the
MarkovGraphhelper used throughout this chapter, until successive iterates barely move. - System of linear equations. \(\boldsymbol{\pi}(\mathbf{I}-\mathbf{M})=\mathbf{0}\) together with \(\sum_i\pi_i=1\) (replacing one redundant equation of the singular system by the normalization constraint, exactly what its \(\texttt{solveStationary}\) method does) is a small linear system, solvable exactly for any \(n\) a computer can hold \(\mathbf{M}\) in memory for.
- Eigenvectors and eigenvalues. Compute all eigenvalues and eigenvectors of \(\mathbf{M}^T\) and read off the one belonging to the eigenvalue \(\lambda=1\), normalized to sum to one.
The last two are not really different computations in disguise, they are the same underlying linear system \(\boldsymbol{\pi}(\mathbf{I}-\mathbf{M})=\mathbf{0}\) approached from two directions: solving it directly is the eigenvector route specialized to the one eigenvalue that matters, so it is no surprise both return identical numbers on the worked example. In practice, however, brute-force power iteration wins decisively over either exact route, despite the eigenvector derivation being the cleanest theoretical justification for why a stationary distribution exists and is unique in the first place: forming or diagonalizing \(\mathbf{M}\) explicitly needs \(n^2\) storage, hopeless once \(n\) is in the billions, but the teleportation term is rank one and never needs to be materialized: since \(\sum_i\pi_{k,i}=1\) throughout, \(\boldsymbol{\pi}_k\mathbf{J}\) is simply the all-ones vector, so
\[\boldsymbol{\pi}_{k+1}=d\,\boldsymbol{\pi}_k\mathbf{H}+\frac{d\,s_k+(1-d)}{n}\mathbf{1},\qquad s_k=\sum_{i\,:\,C(i)=0}\pi_{k,i},\]
where \(\mathbf{H}\) is the original, unpatched (and extremely sparse, since a typical page links to only a handful of others) link matrix and \(s_k\) is the total rank currently parked on dangling pages. Every step costs time proportional to the number of hyperlinks rather than \(n^2\), which is what makes power iteration, and only power iteration, practical at web scale (Bryan & Leise, 2006).
How Fast Does Power Iteration Converge?
As with power iteration in general, the convergence rate is governed by the ratio between the dominant eigenvalue and the second-largest one in magnitude. Haveliwala and Kamvar (2003) show that damping bounds this ratio directly in terms of \(d\): the second eigenvalue of \(\mathbf{M}\) never exceeds \(d\) in absolute value, however the underlying link structure looks. The disconnected two-loop example above realizes this bound exactly, with second eigenvalue \(-0.85=-d\); the four-page worked example is a little faster in practice, with an observed error shrinking by a factor of about \(0.757\) per step once the iteration settles down, comfortably inside the guaranteed bound of \(d=0.85\). Either way, the error after \(k\) steps shrinks like \(O(d^k)\), so a modest number of iterations already gives several correct digits, which is why power iteration converges quickly enough to be run repeatedly on a web-scale graph in practice.
Beyond the Web: Personalized, Text, and Evolving Graphs
The only place the web's specific structure enters the whole derivation is in how \(\mathbf{L}\) is built and how the teleportation vector is chosen; everything else, the damped random walk, the Perron–Frobenius argument, the power-iteration algorithm, applies to any directed graph whatsoever.
Replacing the uniform teleportation vector \(\mathbf{1}/n\) with an arbitrary probability vector concentrated on a chosen set of pages biases the random surfer to return to those pages whenever they get bored, without changing any of the convergence guarantees, since the resulting matrix is still strictly positive as long as every teleportation probability is positive. This is the basis of topic-sensitive PageRank (Haveliwala, 2002), which computes several such biased rank vectors, one per topic, and blends them according to a query's own topical similarity, rather than serving one global ranking to every user. A closely related variant concentrates the teleportation vector on one or a few specific seed vertices instead of a whole topic category, so that rank flows outward from, and decays with distance from, that seed; Haveliwala, Jeh and Kamvar (2003) compare several ways of computing and combining such seed-based personalization vectors efficiently.
The same random-walk machinery also works on graphs that have nothing to do with hyperlinks. In TextRank (Mihalcea & Tarau, 2004), the vertices are words or whole sentences from a document, and edges (or edge weights) come from co-occurrence within a fixed window or from similarity between sentences; running the identical damped power iteration on this graph ranks words for keyword extraction or sentences for extractive summarization, entirely without any hyperlink structure. A related idea, random-walk term weighting (Hassan, Mihalcea & Banea, 2007), builds a word co-occurrence graph per document and uses the resulting stationary distribution as a term-importance score for text classification, in place of frequency-based weighting schemes.
Finally, real graphs, web or otherwise, keep changing: pages and links appear and disappear continuously, and recomputing \(\boldsymbol{\pi}\) from scratch after every change does not scale. Bahmani, Kumar, Mahdian and Upfal (2012) study PageRank on such evolving graphs, and show that sampling new random-walk segments to probe with a frequency proportional to a vertex's own current PageRank, rather than uniformly across all vertices, keeps the estimate accurate while touching only a small fraction of the graph after each batch of changes.
Applications
- Ranking web search results, the original motivating use (Brin & Page, 1998; Page, Brin, Motwani & Winograd, 1999)
- Topic-sensitive and personalized search ranking, biasing results toward a user's or query's own interests (Haveliwala, 2002)
- Keyword extraction and extractive summarization via TextRank (Mihalcea & Tarau, 2004)
- Term weighting for text classification via random walks over word co-occurrence graphs (Hassan, Mihalcea & Banea, 2007)
- Ranking nodes in any other directed graph by influence or prestige, from citation networks to social networks, wherever a graph's structure can be captured in a matrix and importance is naturally recursive
References
- Brin & Page 1998Brin, S., & Page, L. (1998). The Anatomy of a Large-Scale Hypertextual Web Search Engine. Computer Networks and ISDN Systems, 30(1–7), 107–117.
- Page et al. 1999Page, L., Brin, S., Motwani, R., & Winograd, T. (1999). The PageRank Citation Ranking: Bringing Order to the Web. Stanford InfoLab Technical Report.
- Haveliwala & Kamvar 2003Haveliwala, T., & Kamvar, S. (2003). The Second Eigenvalue of the Google Matrix. Stanford University Technical Report.
- Haveliwala 2002Haveliwala, T. (2002). Topic-Sensitive PageRank. Proceedings of the 11th International World Wide Web Conference (WWW).
- Haveliwala et al. 2003Haveliwala, T., Jeh, G., & Kamvar, S. (2003). An Analytical Comparison of Approaches to Personalizing PageRank. Stanford University Technical Report.
- Grolmusz 2015Grolmusz, V. (2015). A Note on the PageRank of Undirected Graphs. Information Processing Letters, 115(6–8), 633–634.
- Mihalcea & Tarau 2004Mihalcea, R., & Tarau, P. (2004). TextRank: Bringing Order into Texts. Proceedings of EMNLP.
- Hassan et al. 2007Hassan, S., Mihalcea, R., & Banea, C. (2007). Random-Walk Term Weighting for Improved Text Classification. Proceedings of TextGraphs-2.
- Bahmani et al. 2012Bahmani, B., Kumar, R., Mahdian, M., & Upfal, E. (2012). PageRank on an Evolving Graph. Proceedings of KDD.
- Bryan & Leise 2006Bryan, K., & Leise, T. (2006). The $25,000,000,000 Eigenvector: The Linear Algebra Behind Google. SIAM Review, 48(3), 569–581.