PageRank
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].
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].
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
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
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]:
Gleich prefers the equivalent linear system
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:
| Page | Backlinks | Score, no damping | Score, $m = 0.15$ |
|---|---|---|---|
| 1 | 2 | 0.387 | 0.368 |
| 2 | 1 | 0.129 | 0.142 |
| 3 | 3 | 0.290 | 0.288 |
| 4 | 2 | 0.194 | 0.202 |
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
| Variant | Year | Change from basic PageRank | Source |
|---|---|---|---|
| Personalized PageRank | 1998 | Jump distribution concentrated on chosen pages, such as a user's home page or bookmarks | [2] |
| Topic-sensitive PageRank | 2002 | 16 vectors biased toward the 16 top-level Open Directory categories, mixed at query time | [12] |
| TrustRank | 2004 | Starts 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 PageRank | various | Transition probabilities proportional to edge weights instead of uniform | [9] |
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].
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].
Role in Google Search
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].
| Field | Example | Source |
|---|---|---|
| Bibliometrics | The Eigenfactor system ranks journals with PageRank ($\alpha = 0.85$) on the journal co-citation network | [9] |
| Bioinformatics | GeneRank uses microarray results as the teleportation vector on a network of known gene relationships | [9] |
| Neuroscience | Ranking brain regions in networks built from correlated brain activity | [9] |
| Transportation | Jiang and colleagues found PageRank ($\alpha = 0.95$) the best network measure for predicting traffic on individual roads | [9] |
| Sports | Filippo Radicchi's PageRank ranking of tennis players placed Jimmy Connors first | [9] |
| Social networks | Ranking Twitter users by importance; localized PageRank is believed to be part of Twitter's follower suggestions | [9] |
| Text processing | TextRank and LexRank rank words or sentences in a graph built from a document | [18][19] |
| Graph learning | Personalized PageRank as the propagation scheme in the APPNP graph neural network | [20] |
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
| PageRank | HITS | |
|---|---|---|
| Introduced | Page, Brin, Motwani and Winograd (report dated 1998) [2] | Kleinberg (IBM report 1997, SODA 1998, JACM 1999) [11] |
| Graph used | The 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 page | One importance score | Separate hub and authority scores that reinforce each other [11] |
| Linear algebra | Stationary distribution of a damped random walk [9] | Dominant singular vectors of the link matrix [8] |
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
- Google SearchGoogle Search is the web search engine operated by Google, a subsidiary of Alphabet, and the most widely used information retrieval service in the worldMentioned twice above
- Markov chainA Markov chain is a stochastic process in which the probability of the next state depends only on the current state and not on the sequence of states that came before it.Listed in See also
- Information RetrievalInformation retrieval (IR) is the study and engineering of systems that identify material likely to satisfy an information need.Listed in See also
- Knowledge graphA knowledge graph is a structured representation of real-world entities and the relationships between them, organized as a network of interconnected nodes and edges.Listed in See also
- Recommendation SystemA recommendation system (also called a recommender system) is an information filtering system that predicts a user's preferences and ranks the items most likely to interest that user, such as the movies…Listed in See also
- GoogleGoogle LLC is a United States technology company and the largest operating business within Alphabet Inc. Its activities include internet search, online advertising, video, mobile and web platforms, consumer…Mentioned 25 times above
More to read
References
- ^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
- ^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
- ^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
- ^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
- ^1 ^2 ^3 ^4 ^5 ^6Google Inc. "Form S-1 Registration Statement". U.S. Securities and Exchange Commission, 2004. sec.gov/...ds1
- ^1 ^2 ^3 ^4Richard Brandt. "Net Assets". Stanford Magazine, November/December 2004. stanfordmag.org/...net-assets
- ^1 ^2Richard Brandt. "Starting Up". Stanford Magazine (online, posted January 26, 2012). stanfordmag.org/...starting-up
- ^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
- ^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
- ^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
- ^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
- ^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
- ^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
- ^1 ^2Matt Cutts and Jason Shellen. "Preventing comment spam". Official Google Blog, January 18, 2005. googleblog.blogspot.com/...preventing-comment-spam
- ^Barry Schwartz. "Google has confirmed it is removing Toolbar PageRank". Search Engine Land, March 8, 2016. searchengineland.com/...ng-toolbar-pagerank-244230
- ^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
- ^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
- ^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
- ^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
- ^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
- ^NetworkX developers. "pagerank". NetworkX 3.7 documentation. networkx.org/...ink_analysis.pagerank_alg.pagerank
- ^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


