--- date: '2024-09-04' description: how pagerank scores pages from links alone, from the 1998 stanford report through the random surfer, dangling pages, convergence and personalization, and how this garden ranks its notes with it. id: PageRank modified: 2026-10-25 11:30:00 GMT-04:00 seealso: - '[[thoughts/Search|Search]]' - '[[pagerank]]' tags: - technical - algorithm title: PageRank created: '2024-09-04' published: '2024-09-04' pageLayout: default slug: thoughts/PageRank permalink: https://aarnphm.xyz/thoughts/PageRank.md generator: quartz: v4.6.0 hostedProvider: Cloudflare baseUrl: aarnphm.xyz full: https://aarnphm.xyz/llms-full.txt --- PageRank computes page scores from a link graph. Larry Page, Sergey Brin, Rajeev Motwani and Terry Winograd describe it in a Stanford report ([Page et al., 1999](http://ilpubs.stanford.edu:8090/422/)); the draft is dated January 29, 1998. The score does not depend on the query, so a [[thoughts/Search|search engine]] computes it once per crawl and uses it for every query. This garden computes the same score over its own notes on [[pagerank|/pagerank]]. ## From citations to links Citation analysis counts how often other papers cite a paper. The report treats a link as a citation, so a page with many backlinks (inbound links) is probably important. Raw backlink counts fail on the web for two reasons. A web page costs nothing to publish, so anyone can make many pages that link to one target. And one link from the Yahoo home page says more about a page than many links from pages that nobody reads. PageRank uses a recursive rule instead: a page has a high rank when the ranks of the pages that link to it add up to a large number. Many backlinks raise a page, and so do a few backlinks from high-ranked pages. A link contributes according to the source page’s rank and outgoing links, so counting backlinks alone misses part of the calculation. ## The simplified rank Let $B_u$ be the set of pages that link to page $u$, and let $N_v$ be the number of links on page $v$. The report first defines $$ R(u) = c \sum_{v \in B_u} \frac{R(v)}{N_v} $$ Each page divides its rank equally among its links, and each page receives the sum of the parts that arrive. The constant $c$ keeps the total rank fixed. The report’s Figure 3 is a small example. A links to B and C, B links to C, and C links to A. The ranks $R(A) = 0.4$, $R(B) = 0.2$, $R(C) = 0.4$ are a fixed point: A sends $0.2$ on each of its two links, C receives $0.2$ from A and $0.2$ from B, and C sends all of its $0.4$ to A. In matrix form, let $M_{uv} = 1/N_v$ when $v$ links to $u$, and $0$ otherwise. Then $R = cMR$, so $R$ is an eigenvector of $M$.[^transpose] If every page has an outgoing link, each column sums to $1$ and $c = 1$. Power iteration repeatedly multiplies an initial probability vector by $M$. It converges to a unique stationary distribution when the finite chain is irreducible and aperiodic. A two-page cycle already breaks convergence: all the mass alternates between the pages if it starts on one of them. Separate closed components can also give several stationary distributions. ## Rank sinks and the random surfer The simplified rule fails on closed loops. Take two pages that link only to each other, and a third page that links to one of them. Rank flows into the pair on every iteration and never leaves. The report calls this a rank sink. The fix is a rank source $E$, a vector over pages: $$ R'(u) = c \sum_{v \in B_u} \frac{R'(v)}{N_v} + c\,E(u), \qquad \lVert R' \rVert_1 = 1 $$ The report explains $E$ with a random surfer who sometimes stops following links and starts elsewhere. Its experiments mostly used a uniform source with $\lVert E \rVert_1 = 0.15$. That source includes both a distribution over destinations and an amount of rank to inject. To separate them, write $E = e v$, where $e = \lVert E \rVert_1$ and $v$ is a probability vector. On a graph where every page has an outgoing link, summing the fixed-point equation gives $$ 1 = c(1+e), \qquad c = \frac{1}{1+e}. $$ The resulting equation is $R' = cMR' + (1-c)v$. Thus the report’s $e = 0.15$ gives $c = 1/1.15 \approx 0.8696$, rather than $0.85$. A source of mass $e = (1-d)/d$ gives a chosen damping factor $d$. This conversion assumes a column-stochastic link matrix; dangling pages need the treatment below. The usual probability-normalized form instead chooses $d = 0.85$ directly. At each step the surfer follows a random link with probability $d$ and restarts from $v$ with probability $1-d$. For uniform $v$, with $N$ pages and $L(q)$ links on page $q$: $$ \mathrm{PR}(p) = \frac{1-d}{N} + d \sum_{q \to p} \frac{\mathrm{PR}(q)}{L(q)} $$ $\mathrm{PR}(p)$ is the long-run fraction of steps that the surfer spends on $p$.[^anatomy] Without the jump, a surfer in a rank sink stays there. At $d = 0.85$, the mean wait until a restart is $1/(1-d) \approx 6.7$ steps. A restart can land in the same sink. For a closed set of $s$ pages under uniform restart, the mean wait to leave is $1/[(1-d)(1-s/N)]$ when $s < N$. ## Dangling pages A page with no links is dangling. Its rank flows nowhere, so the total rank shrinks on every iteration. In 1998 most dangling pages were pages that the crawler had not fetched yet: the 24 million downloaded pages pointed to 51 million URLs that were not downloaded. The report removes dangling pages, computes the ranks of the others, adds the dangling pages back, and iterates a few more times. The usual choice now, and the one this garden makes, keeps dangling pages and treats each one as a link to every page. The surfer on a dangling page jumps at random: $$ \mathrm{PR}(p) = \frac{1-d}{N} + \frac{d}{N}\sum_{L(q)=0}\mathrm{PR}(q) + d \sum_{q \to p} \frac{\mathrm{PR}(q)}{L(q)} $$ With this term the scores always sum to $1$, and no rank is lost. ## Computing it The report’s §2.6 prints the following lost-mass loop: $$ \begin{aligned} R_{i+1} &\leftarrow A R_i \\ \delta_{\text{lost}} &\leftarrow \lVert R_i \rVert_1 - \lVert R_{i+1} \rVert_1 \\ R_{i+1} &\leftarrow R_{i+1} + \delta_{\text{lost}}\, E \\ \delta &\leftarrow \lVert R_{i+1} - R_i \rVert_1 \end{aligned} $$ It repeats until $\delta < \epsilon$. The final addition preserves total mass only if the $E$ used in this loop sums to $1$: multiplying the lost mass by a source of mass $0.15$ replaces only $15\%$ of it. An undamped stochastic $A$ loses no mass at all, so that reading of the loop also supplies no restarts. The report’s displayed source equation and loop therefore need their normalization conventions made explicit before use. (The report names the lost mass $d$; it is a different quantity from the damping factor.) For the probability-normalized model, let $M$ contain the link fractions and a zero column for each dangling page, and keep $v$ normalized. The corresponding mass-preserving update is $$ \begin{aligned} y &\leftarrow dMr_i \\ \ell &\leftarrow 1-\lVert y\rVert_1 \\ r_{i+1} &\leftarrow y+\ell v. \end{aligned} $$ Starting with $\lVert r_i\rVert_1 = 1$, the missing mass is $\ell = 1-d+d\sum_{L(q)=0}r_i(q)$. It includes both scheduled restarts and dangling-page mass. The same $v$ receives both here. The 1998 implementation gave each URL an integer ID and sorted the link table by source page. Only the current weights stayed in memory: 4 bytes for each of 75 million URLs is 300 MB. The sorted link table and the previous weights streamed from disk. One iteration took about 6 minutes on a workstation, and the whole computation took about 5 hours. The report notes that this cost is small next to building the full-text index. On 322 million links the computation reached its tolerance in about 52 iterations. On half the links it took about 45. Twice the data cost about 15% more iterations. The report explains the fast convergence with expander graphs: a random walk mixes in time logarithmic in the size of the graph when the gap between the first and second eigenvalues is large. A sharper result came later. For any link graph with dangling columns repaired, the second eigenvalue of the PageRank matrix satisfies $\lvert\lambda_2\rvert \le d$ ([Haveliwala and Kamvar, 2003](http://ilpubs.stanford.edu:8090/582/)). A direct $L_1$ argument gives the per-step bound. Let $S$ be the column-stochastic matrix after dangling repair and $T(x)=dSx+(1-d)v$. For probability vectors $x$ and $z$, the restart terms cancel: $$ \lVert T(x)-T(z)\rVert_1 = d\lVert S(x-z)\rVert_1 \le d\lVert x-z\rVert_1. $$ For $0