Inside PageRank
The DOI matches its Crossref record; 28 of the 29 references it cites were found in a registry or an index.
Abstract
Although the interest of a Web page is strictly related to its content and to the subjective readers' cultural background, a measure of the page authority can be provided that only depends on the topological structure of the Web. PageRank is a noticeable way to attach a score to Web pages on the basis of the Web connectivity. In this article, we look inside PageRank to disclose its fundamental properties concerning stability, complexity of computational scheme, and critical role of parameters involved in the computation. Moreover, we introduce a circuit analysis that allows us to understand the distribution of the page score, the way different Web communities interact each other, the role of dangling pages (pages with no outlinks), and the secrets for promotion of Web pages.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“The one-to-one correspondence between (4) and (8) was noticed and proved in [2] but we find the proof presented above more insightful in our context.”
From Monte Carlo Methods in PageRank Computation: When One Iteration is Sufficient (2007) · cites this paper as [2]
Citations
Cites
Learning representations by back-propagating errors
Rumelhart, D. E., Hinton, G. E., & Williams, R. J. (1986) · Nature · doi:10.1038/323533a0 · Cited by 31,892
The anatomy of a large-scale hypertextual Web search engine
Brin, S., & Page, L. (1998) · Computer Networks and ISDN Systems · doi:10.1016/s0169-7552(98)00110-x · Cited by 16,004 · cited 5×
“The above stochastic interpretation of PageRank is slightly different from those presented in Brin and Page [1998], Ng et al. [2001a], and Lempel and Moran [2000]. In fact, PageRank is usually modeled using the classical random walk theory on graphs, with the following assumptions:”
BackgroundMethodInfluential(1999) · Cited by 12,854
Authoritative sources in a hyperlinked environment
Kleinberg, J. M. (1999) · Journal of the ACM · doi:10.1145/324133.324140 · Cited by 8,959
Motwani, R., & Raghavan, P. (1995) · Cambridge University Press eBooks · doi:10.1017/cbo9780511814075 · Cited by 5,123
Numerical Methods for Least Squares Problems
Björck, Å. (1996) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611971484 · Cited by 3,257 · cited 5×
“More generally, the same idea is found for the estimation of qualifications in self-evaluating groups [Bomze and Gutjahr 1994, 1995]. Here, each member of a group or an institution produces a judgment for all the other members of the same group. PageRank is used by Google together with a number of different factors, i…”
BackgroundInfluentialNumerical methods for least squares problems
(1996) · Choice Reviews Online · doi:10.5860/choice.34-1602 · Cited by 3,007
Non-negative Matrices and Markov Chains
Seneta, E. (1981) · Springer Series in Statistics · doi:10.1007/0-387-32792-4 · Cited by 2,807
Haveliwala, T. H. (2002) · Proceedings of the 11th international conference on World Wide Web · doi:10.1145/511446.511513 · Cited by 1,567
Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI 2017)
Amendola, G., Ricca, F., & Truszczyński, M. (2017) · International Joint Conference on Artificial Intelligence · Cited by 1,179
Improved Algorithms for Topic Distillation in a Hyperlinked Environment
Bharat, K., & Henzinger, M. R. (2017) · ACM SIGIR Forum · doi:10.1145/3130348.3130367 · Cited by 676
The stochastic approach for link-structure analysis (SALSA) and the TKC effect
Lempel, R., & Moran, S. (2000) · Computer Networks · doi:10.1016/s1389-1286(00)00034-7 · Cited by 481 · cited 3×
“[2001a] and Lempel and Moran [2000], each dangling page is assumed to be a special node pointing to all the pages (see Section (2.”
MethodImproved algorithms for topic distillation in a hyperlinked environment
Bharat, K., & Henzinger, M. R. (1998) · Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval · doi:10.1145/290941.290972 · Cited by 444 · cited 2×
“Starting from PageRank and HITS, some extensions have been proposed by hybrid solutions [Zhang and Dong 2000; Bharat and Henzinger 1998; Diligenti et al. 2002; Richardson and Domingos 2002; Haveliwala 2002; Borodin et al. 2001].”
MethodThe Missing Link - A Probabilistic Model of Document Content and Hypertext Connectivity
Cohn, D. A., & Hofmann, T. (2000) · Cited by 436
(1999) · Cited by 293
Stable algorithms for link analysis
Ng, A. Y., Zheng, A. X., & Jordan, M. I. (2001) · Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval · doi:10.1145/383952.384003 · Cited by 286 · cited 2×
“In order to explain the computational properties of the algorithm, most of the authors [Ng et al. 2001b; Zhang and Dong 2000; Brin et al. 1999] cite the general theory of Markov chains [Motwani and Raghavan 1995; Seneta 1981].”
MethodResultLearning to Probabilistically Identify Authoritative Documents
Cohn, D. A., & Chang, H. (2000) · International Conference on Machine Learning · Cited by 269
Finding authorities and hubs from link structures on the World Wide Web
Borodin, A., Roberts, G. O., Rosenthal, J. S., & Tsaparas, P. (2001) · Proceedings of the 10th international conference on World Wide Web · doi:10.1145/371920.372096 · Cited by 230
Hyperlink analysis for the Web
Henzinger, M. R. (2001) · IEEE Internet Computing · doi:10.1109/4236.895141 · Cited by 210
Link Analysis, Eigenvectors and Stability
Ng, A. Y., Zheng, A. X., & Jordan, M. I. (2001) · Cited by 206
The quest for correct information on the Web: hyper search engines
Marchiori, M. (1997) · Computer Networks and ISDN Systems · doi:10.1016/s0169-7552(97)00036-6 · Cited by 191
What can you do with a Web in your Pocket
Brin, S., Motwani, R., Page, L. M., & Winograd, T. A. (1998) · Cited by 140
An efficient algorithm to rank Web resources
Zhang, D., & Dong, Y. (2000) · Computer Networks · doi:10.1016/s1389-1286(00)00056-6 · Cited by 58 · cited 1×
“By the Stein Rosenberg Theorem [Varga 1962], the Gauss-Seidel method is always faster than the Jacobi procedure, when ai,i =0 for each i, ai, j =0 for each i, j , and .”
MethodWeb page scoring systems for horizontal and vertical search
Diligenti, M., Gori, M., & Maggini, M. (2002) · International World Wide Web Conference (WWW) · doi:10.1145/511446.511512 · Cited by 55
Self-citationWhat is a tall poppy among Web pages?
Pringle, G., Allison, L., & Dowe, D. L. (1998) · Computer Networks and ISDN Systems · doi:10.1016/s0169-7552(98)00061-0 · Cited by 36 · cited 1×
“This phenomenon is usually referred to as search engine persuasion or Web spamming [Marchiori 1997; Pringle et al. 1998].”
BackgroundOptimal algorithms for well-conditioned nonlinear systems of equations
Bianchini, M., Fanelli, S., & Gori, M. (2001) · IEEE Transactions on Computers · doi:10.1109/12.936235 · Cited by 21 · cited 1×
“, Björck [1996] and Bianchini et al. [2001]) in a number of steps which is independent of the Web dimension, thus confirming the result stated by Theorem 6.”
ResultSelf-citationEstimating qualifications in a self-evaluating group
Bomze, I. M., & Gutjahr, W. J. (1995) · Quality & Quantity · doi:10.1007/bf01101972 · Cited by 9
The dynamics of self-evaluation
Bomze, I. M., & Gutjahr, W. J. (1994) · Applied Mathematics and Computation · doi:10.1016/0096-3003(94)90138-4 · Cited by 5 · cited 1×
“More generally, the same idea is found for the estimation of quali.cations in self-evaluating groups [Bomze and Gutjahr 1994, 1995].”
Background
Research works printed but not linked: 2
- Golub , G. H. and Van Loan , C. F. 1993. Matrix computation . The Johns Hopkins University Press . Golub, G. H. and Van Loan, C. F. 1993. Matrix computation. The Johns Hopkins University Press.
- Richardson M. and Domingos P. 2002. The intellingent surfer: probabilistic combination of link and content information in pagerank. In Advances in Neural Information Processing Systems 14. MIT Press Cambridge Mass. Richardson M. and Domingos P. 2002. The intellingent surfer: probabilistic combination of link and content information in pagerank. In Advances in Neural Information Processing Systems 14. MIT Press Cambridge Mass.
Cited by
Combating Web Spam with TrustRank
Gyöngyi, Z., Garcia-Molina, H., & Pedersen, J. (2004) · Proceedings 2004 VLDB Conference · doi:10.1016/b978-012088469-8.50052-8 · Cited by 1,085
“o = [1, 1, 1, 1, 0, 0, 0], t0 = [1, 12 , 1, 1 2 , 1 2 , 0, 1 2 ].”
BackgroundInfluentialLangville, A., & Meyer, C. (2004) · Internet Mathematics · doi:10.1080/15427951.2004.10129091 · Cited by 894
“These bounds are similar in spirit to the bounds of Ng et al. [94] and Bianchini et al. [19] presented in section 7.”
BackgroundMethodResultInfluentialElectrode Degradation in Lithium-Ion Batteries
Pender, J. P., Jha, G., Youn, D. H., Ziegler, J. M., Andoni, I., Choi, E. J., Heller, A., Dunn, B. S., Weiss, P. S., Penner, R. M., et al. (2020) · ACS Nano · doi:10.1021/acsnano.9b04365 · Cited by 873
Gleich, D. F. (2015) · SIAM Review · doi:10.1137/140976649 · Cited by 646
Virtual network embedding through topology-aware node ranking
Cheng, X., Su, S., Zhang, Z., Wang, H., Yang, F., Luo, Y., & Wang, J. (2011) · ACM SIGCOMM Computer Communication Review · doi:10.1145/1971162.1971168 · Cited by 544
“, Algorithm 1) has been shown to yield any desired precision with a number of iterations proportional to max{1,−log } [6].”
Background
Metadata
- Authors
- Bianchini, M., Gori, M., & Scarselli, F.
- Affiliations
- University of Siena (IT)
- Venue
- ACM Transactions on Internet Technology
- Published
- 2005-02
- Volume
- 5
- Issue
- 1
- Pages
- 92-128
- ISSN
- 1533-5399 (ISSN-L)
- 1557-6051
- OpenAlex
- W2293888960
- Cited by
- 539
- References
- 29
- Citations by year
- 2026: 15 · 2025: 25 · 2024: 30 · 2023: 23 · 2022: 20 · 2021: 17 · 2020: 21 · 2019: 16 · 2018: 18 · 2017: 24 · 2016: 25 · 2015: 20 · 2014: 21 · 2013: 26 · 2012: 30
- FWCI
- 98.85
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- ACM Transactions on Internet Technology (publishedVersion)
- Use Siena air (University of Siena) (submittedVersion)
- Topics
- Physical Sciences › Computer Science › Information Systems › Information Retrieval and Search Behavior
- Physical Sciences › Computer Science › Information Systems › Web visibility and informetrics
- Physical Sciences › Physics and Astronomy › Statistical and Nonlinear Physics › Complex Network Analysis Techniques
- Keywords
- PageRank, web connectivity, computational complexity, damping parameter, online communities, circuit analysis
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.