Citation and evidence

PageRank

20 min full readUpdated 22 references

This article's verification

Report a problem with this article

Edit article
More

Use this article

Raw MarkdownExplore connections

Improve this page

Revision historyDiscuss this article

Topics

AlgorithmsGoogleInformation RetrievalMathematics

Cite this article

PageRank is a link-analysis algorithm that scores the importance of every page in a hyperlinked collection from the structure of the links between pages, giving more weight to links that come from pages which are themselves important. Larry Page and Sergey Brin developed it as graduate students at Stanford University and described it in 1998 as one of the two main features of their prototype search engine, Google [1][2]. Mathematically, a page's PageRank is its probability in the stationary distribution of a "random surfer" who follows links at random and occasionally jumps to a page chosen independently of the current one [2][9]. Stanford patented the method with Page as the inventor and licensed it to Google, exclusively until 2011 [3][5]. The same mathematics has since been applied to citation networks, biology, road networks, social networks, natural language processing and graph neural networks [9][18][20].

Network of eleven circles labelled with PageRank percentages; B (38.4%) and C (34.3%) are largest, joined by arrows
PageRank values, shown as percentages, for a small network of eleven linked pages with a damping factor of 0.85. en:User:345Kai, User:Stannered, via Wikimedia Commons, Public domain.

History

Origins at Stanford

Hector Garcia-Molina, Page's adviser, recalled in 2004 that Page came to his office in 1995 to show him that the AltaVista search engine could list the pages linking to a given site, and suggested that this link information could be used to rank sites [6]. The research was carried out in Stanford's computer science database group, much of it funded through the government-backed Digital Library Initiative, and the name PageRank comes from Larry Page [6]. The patent records that the work was supported in part by a National Science Foundation grant [3].

The method was described in two documents. The technical report "The PageRank Citation Ranking: Bringing Order to the Web", by Page, Brin, Rajeev Motwani and Terry Winograd, is dated 29 January 1998 on its first page and was issued as a Stanford InfoLab technical report in 1999 [2]. It gives the full mathematical definition, the computation, and experiments on personalization and traffic estimation. The better-known paper "The Anatomy of a Large-Scale Hypertextual Web Search Engine", by Brin and Page, appeared in the journal Computer Networks and ISDN Systems in April 1998 and presented Google as a prototype with a full-text and hyperlink database of at least 24 million pages [1]. That paper names PageRank and anchor text as the two important features that help Google produce high-precision results, and refers readers to the technical report for details [1].

Precursors

The idea of scoring an entity recursively by the scores of those that endorse it is much older than the web. In a history of what he calls spectral ranking, Sebastiano Vigna traces it to Edmund Landau, who in 1895 proposed ranking chess players by an eigenvector of the matrix of game results, and to John R. Seeley, who in 1949 argued that an index of importance should be defined recursively, so that each entity's score is a weighted sum of the scores of the entities that endorse it [8]. Leo Katz added a damping or attenuation factor in 1953, and Gabriel Pinski and Francis Narin applied eigenvector ranking to journal citation counts in 1976 [8]. Vigna writes that PageRank is a damped "Markovian" spectral ranking of the web graph, and that with a uniform preference vector it is almost identical to a "total effect centrality" defined by Friedkin in 1991 [8]. David Gleich's survey identifies teleportation, the random jump, as the feature of the PageRank random walk that had not appeared in earlier literature [9].

On the web itself, Jon Kleinberg's hubs-and-authorities method (HITS) was developed at about the same time; preliminary versions appeared as an IBM research report in May 1997 and at the ACM-SIAM Symposium on Discrete Algorithms in 1998 [11]. The PageRank technical report cites it as "an interesting model of the web as Hubs and Authorities" [2]. The PageRank patent's list of cited references includes Kleinberg's paper, Massimo Marchiori's 1997 "hyper search engine" paper, the Pinski and Narin paper, and U.S. Patent 5,920,859, "Hypertext document retrieval system and method", whose inventor is Yanhong Li [3][4]. Li, known in English as Robin Li and later a co-founder of Baidu, developed the link-analysis search system he called RankDex in 1996 while working for IDD Information Services, a division of Dow Jones [22]. His patent, filed on 5 February 1997 and assigned to IDD Enterprises, ranks documents for a query by comparing the query with the anchor text of hyperlinks that point to each document [4]. Vigna notes that using links to adjust text-based scores goes back at least to the late 1980s, and that Marchiori's method does not perform any kind of spectral ranking [8].

"M4ML - Linear Algebra - 5.7 Introduction to PageRank", video from Digital Media - Imperial College London, published November 15, 2019. Watch on YouTube.

How PageRank works

The basic idea

Counting backlinks treats every link equally. PageRank instead holds that a link from an important page is worth more than a link from an obscure one, and that a page which links to many others passes on only a fraction of its importance through each link [1][2]. The technical report gives the intuition that a page has a high rank if the sum of the ranks of its backlinks is high, which covers both a page with many backlinks and a page with a few highly ranked ones [2].

In the simplest form, discussed in an expository article by Kurt Bryan and Tanya Leise, the score $x_k$ of page $k$ satisfies

xk=∑j∈Lkxjnjx_k = \sum_{j \in L_k} \frac{x_j}{n_j}

where $L_k$ is the set of pages that link to page $k$ and $n_j$ is the number of outgoing links on page $j$ [10]. Written as a matrix equation $Ax = x$, this asks for an eigenvector with eigenvalue 1 of the link matrix $A$, whose entry $A_{ij}$ is $1/n_j$ when page $j$ links to page $i$ [10].

Random surfer model

Brin and Page explained the score as a model of user behavior: a "random surfer" starts on a random page, keeps clicking links without ever pressing "back", and eventually gets bored and jumps to another random page [1]. The probability that the surfer visits a given page is that page's PageRank [1]. The paper describes the damping factor $d$ as the probability that the surfer gets bored and requests a random page [1]; in later treatments the parameter is read the other way round, as the probability $\alpha$ of following a link, with $1-\alpha$ the probability of a random jump [9]. The technical report describes the same model as the standing probability distribution of a random walk on the graph of the web, with the jump added because a real surfer caught in a small loop of pages would not stay there forever [2].

The 1998 formula

The Anatomy paper defines the PageRank of a page $A$, linked to by pages $T_1, \dots, T_n$, as

PR(A)=(1−d)+d(PR(T1)C(T1)+⋯+PR(Tn)C(Tn))PR(A) = (1-d) + d\left(\frac{PR(T_1)}{C(T_1)} + \cdots + \frac{PR(T_n)}{C(T_n)}\right)

where $C(T_i)$ is the number of links going out of page $T_i$ and $d$ is a damping factor between 0 and 1 that the authors "usually set" to 0.85 [1]. The paper states that PageRank can be computed with a simple iterative algorithm and corresponds to the principal eigenvector of the normalized link matrix of the web [1].

Matrix formulation

Later treatments write PageRank in matrix form. In Gleich's notation, $P$ is a column-stochastic matrix whose entry $P_{ij}$ is the probability of moving from page $j$ to page $i$, $v$ is a teleportation distribution (a probability vector), $e$ is the vector of all ones and $0 < \alpha < 1$ is the teleportation parameter, which plays the role of $d$. The PageRank vector $x$ is the stationary distribution of the resulting Markov chain [9]:

(αP+(1−α)veT)x=x\left(\alpha P + (1-\alpha) v e^{T}\right) x = x

Gleich prefers the equivalent linear system

(I−αP) x=(1−α) v(I - \alpha P)\,x = (1-\alpha)\,v

because existence and uniqueness of a non-negative solution follow immediately (the matrix $I - \alpha P$ is a diagonally dominant M-matrix), and he notes that many authors take the eigensystem as the definition instead [9]. Bryan and Leise give the same construction for a uniform jump as $M = (1-m)A + mS$, where every entry of $S$ is $1/n$ and $m$ corresponds to $1-\alpha$; they show that this mixing makes the ranking unique even when the web splits into disconnected parts, a case in which the plain link matrix has more than one independent eigenvector with eigenvalue 1 [10].

Rank sinks and dangling pages

The technical report identifies two structural problems. A "rank sink" is a group of pages, such as two pages that link only to each other, that accumulates rank during iteration without passing any on; the jump vector, called $E$ in the report, was introduced as a source of rank to overcome it [2]. "Dangling links" point to pages with no outgoing links, often pages that had not yet been downloaded: in the 24 million pages crawled at the time there were 51 million such URLs [2]. The authors removed dangling links while computing PageRank and added them back afterwards [2]. Bryan and Leise note that the damping modification alone does not resolve dangling nodes [10], and Gleich's survey catalogs several later conventions for handling them [9].

Worked example

Bryan and Leise use a web of four pages in which page 1 links to pages 2, 3 and 4; page 2 links to pages 3 and 4; page 3 links only to page 1; and page 4 links to pages 1 and 3 [10]. Counting backlinks would make page 3 the most important, since every other page links to it. The PageRank-style scores tell a different story:

PageBacklinksScore, no dampingScore, $m = 0.15$
120.3870.368
210.1290.142
330.2900.288
420.1940.202

Expanded article table

Page 1 comes first because page 3 casts its whole vote for page 1 [10]. Without damping the exact scores are 12/31, 4/31, 9/31 and 6/31 [10].

Computation and convergence

The standard method is power iteration: start from a probability vector and repeatedly apply the update $x^{(k+1)} = \alpha P x^{(k)} + (1-\alpha) v$ [9]. Gleich shows that the error in the 1-norm after $k$ iterations is at most $2\alpha^k$ when starting from $v$, so the error shrinks by at least a factor $\alpha$ per step regardless of the size of the graph [9]. Bryan and Leise note that the second largest eigenvalue of the damped matrix is at most $1-m$ in magnitude, which governs how fast the power method converges [10].

The 1998 technical report gives figures from the original system. Ranks were held as 4-byte single-precision values, which came to 300 megabytes for 75 million URLs; each iteration over the link database took about 6 minutes on a typical workstation, and the whole process, including adding dangling links back, took about five hours [2]. On a database of 322 million links, PageRank converged to a reasonable tolerance in roughly 52 iterations, against roughly 45 for half the data, which the authors read as evidence that the computation would scale well [2]. They related the fast convergence to the theory of rapidly mixing random walks, describing the web as an "expander-like graph" [2]. The Anatomy paper reported that PageRank for 26 million pages could be computed in a few hours on a medium-size workstation [1].

Variants

VariantYearChange from basic PageRankSource
Personalized PageRank1998Jump distribution concentrated on chosen pages, such as a user's home page or bookmarks[2]
Topic-sensitive PageRank200216 vectors biased toward the 16 top-level Open Directory categories, mixed at query time[12]
TrustRank2004Starts from a small hand-checked seed set of reputable pages and uses the link structure to find other good pages, to separate them from spam[13]
Weighted PageRankvariousTransition probabilities proportional to edge weights instead of uniform[9]

Expanded article table

The technical report already treated the jump vector as a tuning parameter. With a uniform vector of total weight 0.15, pages such as copyright warnings, disclaimers and heavily interlinked mailing-list archives received overly high ranks; when the jump was concentrated on a single page, the mailing-list problem did not occur [2]. The authors computed rankings from the point of view of the Netscape home page and of the home page of John McCarthy, and found that computer science pages, especially Stanford ones, ranked higher in the McCarthy view [2]. They suggested that such personalized rankings could power personal search engines [2].

Taher Haveliwala's topic-sensitive PageRank (2002) precomputes a set of PageRank vectors, each biased by the URLs under one of the 16 top-level categories of the Open Directory Project, and combines them at query time according to the topics of the query [12]. Glen Jeh's work with Jennifer Widom on scaling personalized search, and later work by Haveliwala and Sepandar Kamvar on making it efficient, led the three to found a company called Kaltix, which Google acquired within months, according to a 2004 Stanford Magazine account [6].

TrustRank, proposed by Zoltán Gyöngyi, Hector Garcia-Molina and Jan Pedersen at the 2004 VLDB conference, has an expert label a small set of seed pages and then uses the link structure to find other pages likely to be reputable; in experiments on the web as indexed by AltaVista, a good seed set of fewer than 200 sites filtered spam out of a significant fraction of the web [13].

Patent and licensing

U.S. Patent 6,285,999, "Method for node ranking in a linked database", names Lawrence Page as the inventor and the Board of Trustees of the Leland Stanford Junior University as the original assignee [3]. Its abstract describes ranking a document from the ranks of documents citing it, together with a constant representing the probability that a browser will jump to the document at random [3].

DateEventSource
1997-01-10Provisional application 60/035,205 filed[3]
1998-01-09Patent application filed[3]
2001-09-04Patent granted[3]
2003-10Google extends its exclusive license through 2011[5]
2018-01-09Anticipated expiration listed by Google Patents[3]

Expanded article table

Stanford's Office of Technology Licensing first tried to sell or license the technology to existing companies, but no buyer would pay the million-dollar asking price; Page and Brin then started their own company with an exclusive license to the patent [7]. As the patent holder, Stanford received more than 1.8 million shares of Google [7]. Google's 2004 registration statement for its initial public offering said that Stanford owned a patent on PageRank, that Google held a perpetual license, and that the license would become non-exclusive after 2011 [5]. Google Patents lists the patent's status as expired [3].

Google's 2004 offering document described PageRank as a query-independent technique that treats a link from page A to page B as a "vote" by page A for page B, with votes from pages of high PageRank weighing more [5]. The same document said that Google had developed much of its ranking technology after the company was formed, that PageRank had been published because it was developed as research at Stanford, and that most of Google's current ranking technology was protected as a trade secret [5].

From 2000, the Google Toolbar for Internet Explorer could show a PageRank meter that reported a score from 0 to 10 for any page being viewed [16]. Danny Sullivan of Search Engine Land later argued that the visible score made search engine optimization practitioners fixate on a single metric and fed a market for buying and selling links [16]. Google penalized the SearchKing link network, which sued and lost after a judge held that Google's results were protected opinions under the First Amendment [16]. In January 2005 Google announced that links carrying the attribute rel="nofollow" would receive no credit in its rankings, aimed at comment spam on blogs, with support from several blog software makers, MSN Search and Yahoo! [14]. Sullivan reported that PageRank scores were dropped from Google Search Console in 2009, that Firefox support for the toolbar ended in 2011, and that the toolbar scores were last refreshed in 2013 [16]. In March 2016 Google confirmed to Search Engine Land that it was removing Toolbar PageRank entirely, while saying that it still used PageRank data internally in its ranking algorithm [15].

As of November 2026, Google's public guide to its ranking systems lists "Link analysis systems and PageRank" among them, describes PageRank as one of the core ranking systems used when Google first launched, and says that how PageRank works "has evolved a lot since then" and that it remains part of the core ranking systems [17]. The same guide also lists systems such as RankBrain [17].

Applications beyond the web

Gleich's 2015 survey in SIAM Review argues that the mathematics of PageRank applies to any graph, and that its simplicity, generality, guaranteed existence and uniqueness, and fast computation explain its spread [9]. He distinguishes two uses: as a global centrality measure with near-uniform teleportation, and as a localized tool that teleports to a few chosen nodes to explore one region of a large graph [9].

FieldExampleSource
BibliometricsThe Eigenfactor system ranks journals with PageRank ($\alpha = 0.85$) on the journal co-citation network[9]
BioinformaticsGeneRank uses microarray results as the teleportation vector on a network of known gene relationships[9]
NeuroscienceRanking brain regions in networks built from correlated brain activity[9]
TransportationJiang and colleagues found PageRank ($\alpha = 0.95$) the best network measure for predicting traffic on individual roads[9]
SportsFilippo Radicchi's PageRank ranking of tennis players placed Jimmy Connors first[9]
Social networksRanking Twitter users by importance; localized PageRank is believed to be part of Twitter's follower suggestions[9]
Text processingTextRank and LexRank rank words or sentences in a graph built from a document[18][19]
Graph learningPersonalized PageRank as the propagation scheme in the APPNP graph neural network[20]

Expanded article table

In natural language processing, Rada Mihalcea and Paul Tarau's TextRank (2004) applies graph-based ranking in the style of PageRank and HITS to graphs of words or sentences for unsupervised keyword and sentence extraction [18]. LexRank, by Güneş Erkan and Dragomir Radev, scores sentences by eigenvector centrality in a graph whose edges come from cosine similarity between sentences; a system based on it ranked first in more than one task at the DUC 2004 evaluation [19]. Both methods are standard techniques in extractive text summarization.

In graph machine learning, Johannes Gasteiger (then Klicpera), Aleksandar Bojchevski and Stephan Günnemann used the relationship between graph convolutional networks and PageRank to build a propagation scheme based on personalized PageRank. Their models, PPNP and its fast approximation APPNP (ICLR 2019), let a node classifier draw on a large, adjustable neighborhood for semi-supervised learning on graphs [20]. PageRank is also a standard routine in graph software; the NetworkX library's pagerank function, for example, computes it by power iteration with a default damping parameter of 0.85 [21].

Comparison with HITS

PageRankHITS
IntroducedPage, Brin, Motwani and Winograd (report dated 1998) [2]Kleinberg (IBM report 1997, SODA 1998, JACM 1999) [11]
Graph usedThe whole crawled web, independent of any query [2][5]A focused subgraph built from a text search engine's results for one query [11]
Scores per pageOne importance scoreSeparate hub and authority scores that reinforce each other [11]
Linear algebraStationary distribution of a damped random walk [9]Dominant singular vectors of the link matrix [8]

Expanded article table

Limitations and criticism

The technical report argued that personalized PageRanks were "virtually immune to manipulation by commercial interests", because a page could only gain rank by persuading important pages or many unimportant pages to link to it, and it described buying links on important sites as "well under control since it costs money" [2]. The same section conceded that a jump vector built from all root-level pages of web servers would allow manipulation through large numbers of servers pointing at one site [2]. In practice, link selling and link networks grew around PageRank, prompting Google's penalties and the nofollow attribute described above [14][16]. Gyöngyi and colleagues described link-based spam in which many bogus pages point at a single target to raise its rank [13].

Other criticism concerns effects on the web. In 2004 Stanford Magazine reported that studies by Junghoo Cho, then an assistant professor at UCLA, indicated that Google in effect drove more and more traffic to fewer and fewer sites: the most linked sites were retrieved first, so they were visited more often and attracted still more links [6]. On the technical side, Gleich notes that the basic iteration has good convergence properties when $\alpha$ is not too close to 1 [9], and the original implementation temporarily removed dangling links during the computation [2].

Continue reading

More to read

Topics:AlgorithmsGoogleInformation RetrievalMathematics

References

  1. ^1 ^2 ^3 ^4 ^5 ^6 ^7 ^8 ^9 ^10Sergey Brin and Lawrence Page. "The Anatomy of a Large-Scale Hypertextual Web Search Engine". Computer Networks and ISDN Systems 30(1-7):107-117, April 1998. infolab.stanford.edu/...google
  2. ^1 ^2 ^3 ^4 ^5 ^6 ^7 ^8 ^9 ^10 ^11 ^12 ^13 ^14 ^15 ^16 ^17 ^18 ^19 ^20 ^21 ^22Lawrence Page, Sergey Brin, Rajeev Motwani and Terry Winograd. "The PageRank Citation Ranking: Bringing Order to the Web". Technical Report, Stanford InfoLab, 1999. ilpubs.stanford.edu/422
  3. ^1 ^2 ^3 ^4 ^5 ^6 ^7 ^8 ^9 ^10Lawrence Page (inventor), Leland Stanford Junior University (assignee). "Method for node ranking in a linked database". U.S. Patent 6,285,999 B1, Google Patents, granted 2001-09-04. patents.google.com/...en
  4. ^1 ^2Yanhong Li (inventor), IDD Enterprises LP (assignee). "Hypertext document retrieval system and method". U.S. Patent 5,920,859 A, Google Patents, published 1999-07-06. patents.google.com/...en
  5. ^1 ^2 ^3 ^4 ^5 ^6Google Inc. "Form S-1 Registration Statement". U.S. Securities and Exchange Commission, 2004. sec.gov/...ds1
  6. ^1 ^2 ^3 ^4Richard Brandt. "Net Assets". Stanford Magazine, November/December 2004. stanfordmag.org/...net-assets
  7. ^1 ^2Richard Brandt. "Starting Up". Stanford Magazine (online, posted January 26, 2012). stanfordmag.org/...starting-up
  8. ^1 ^2 ^3 ^4 ^5Sebastiano Vigna. "Spectral Ranking". arXiv:0912.0238 (v15, February 2019); also Network Science 4(4):433-445, 2016. arxiv.org/...0912.0238
  9. ^1 ^2 ^3 ^4 ^5 ^6 ^7 ^8 ^9 ^10 ^11 ^12 ^13 ^14 ^15 ^16 ^17 ^18 ^19 ^20David F. Gleich. "PageRank Beyond the Web". SIAM Review 57(3):321-363, 2015. arxiv.org/...1407.5107
  10. ^1 ^2 ^3 ^4 ^5 ^6 ^7 ^8Kurt Bryan and Tanya Leise. "The $25,000,000,000 Eigenvector: The Linear Algebra behind Google". SIAM Review 48(3):569-581, 2006. doi.org/...050623280
  11. ^1 ^2 ^3 ^4Jon M. Kleinberg. "Authoritative Sources in a Hyperlinked Environment". Journal of the ACM 46(5):604-632, September 1999. cs.cornell.edu/...auth.pdf
  12. ^1 ^2Taher H. Haveliwala. "Topic-Sensitive PageRank". Proceedings of the 11th International Conference on World Wide Web, pp. 517-526, May 2002. doi.org/...511446.511513
  13. ^1 ^2 ^3Zoltán Gyöngyi, Hector Garcia-Molina and Jan Pedersen. "Combating Web Spam with TrustRank". Proceedings of the 30th VLDB Conference, Toronto, 2004. vldb.org/...RS15P3.PDF
  14. ^1 ^2Matt Cutts and Jason Shellen. "Preventing comment spam". Official Google Blog, January 18, 2005. googleblog.blogspot.com/...preventing-comment-spam
  15. ^Barry Schwartz. "Google has confirmed it is removing Toolbar PageRank". Search Engine Land, March 8, 2016. searchengineland.com/...ng-toolbar-pagerank-244230
  16. ^1 ^2 ^3 ^4 ^5Danny Sullivan. "RIP Google PageRank score: A retrospective on how it ruined the web". Search Engine Land, March 9, 2016. searchengineland.com/...erank-retrospective-244286
  17. ^1 ^2Google Search Central. "A guide to Google Search ranking systems". Google for Developers, last updated 2025-12-10. developers.google.com/...ranking-systems-guide
  18. ^1 ^2 ^3Rada Mihalcea and Paul Tarau. "TextRank: Bringing Order into Text". Proceedings of the 2004 Conference on Empirical Methods in Natural Language Processing, pp. 404-411, Barcelona, July 2004. aclanthology.org/W04-3252
  19. ^1 ^2Güneş Erkan and Dragomir R. Radev. "LexRank: Graph-based Lexical Centrality as Salience in Text Summarization". Journal of Artificial Intelligence Research 22:457-479, 2004. doi.org/...jair.1523
  20. ^1 ^2 ^3Johannes Gasteiger (formerly Klicpera), Aleksandar Bojchevski and Stephan Günnemann. "Predict then Propagate: Graph Neural Networks meet Personalized PageRank". International Conference on Learning Representations (ICLR), 2019. arxiv.org/...1810.05997
  21. ^NetworkX developers. "pagerank". NetworkX 3.7 documentation. networkx.org/...ink_analysis.pagerank_alg.pagerank
  22. ^Ellen Elder. "Robin Li". EBSCO Research Starters (Biography), 2013. ebsco.com/...robin-li

Improve this article

Add missing citations, update stale details, or write a clearer explanation. Anyone can edit: changes go live when you publish, and every edit is checked by an editor.

2 revisions · v2 · 4,067 words · full history

Fact-checks are independent of edits: a reviewer re-verifies the article against its sources and stamps the date. How we verify

Research and drafting on this wiki are AI-assisted, under named human editorial standards. How AI is used here

Reviewer note: Independent fact-check before publication on November 18, 2026: 96 claims checked against 24 cited and independent sources; 0 material and 3 minor corrections applied before publication.

Cite this page: AI Wiki. "PageRank." aiwiki.ai, updated 18 Nov 2026, fact-checked 18 Nov 2026. CC BY 4.0. https://aiwiki.ai/wiki/pagerank

Edit article