The DOI matches its Crossref record; 20 of the 20 references it cites were found in a registry or an index.
Extrapolation methods for accelerating PageRank computations
Abstract
We present a novel algorithm for the fast computation of PageRank, a hyperlink-based estimate of the ''importance'' of Web pages. The original PageRank algorithm uses the Power Method to compute successive iterates that converge to the principal eigenvector of the Markov matrix representing the Web link graph. The algorithm presented here, called Quadratic Extrapolation, accelerates the convergence of the Power Method by periodically subtracting off estimates of the nonprincipal eigenvectors from the current iterate of the Power Method. In Quadratic Extrapolation, we take advantage of the fact that the first eigenvalue of a Markov matrix is known to be 1 to compute the nonprincipal eigenvectors using successive iterates of the Power Method. Empirically, we show that using Quadratic Extrapolation speeds up PageRank computation by 25-300% on a Web graph of 80 million nodes, with minimal overhead. Our contribution is useful to the PageRank community and the numerical linear algebra community in general, as it is a fast method for determining the dominant eigenvector of a matrix that is too large for standard fast methods to be practical.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Golub, G. (2012) · doi:10.56021/9781421407944 · Cited by 34,505
Self-citation(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
(2008) · Choice Reviews Online · doi:10.5860/choice.45-5628 · Cited by 2,725
Probability and Random Processes
(2004) · Elsevier eBooks · doi:10.1016/b978-0-12-172651-5.x5000-3 · Cited by 2,535
Haveliwala, T. H. (2002) · Proceedings of the 11th international conference on World Wide Web · doi:10.1145/511446.511513 · Cited by 1,567
Self-citationFocused crawling: a new approach to topic-specific Web resource discovery
Chakrabarti, S., van den Berg, M., & Dom, B. (1999) · Computer Networks · doi:10.1016/s1389-1286(99)00052-3 · Cited by 1,486
Scaling personalized web search
Jeh, G., & Widom, J. (2003) · Proceedings of the twelfth international conference on World Wide Web - WWW '03 · doi:10.1145/775152.775191 · Cited by 1,195
The Web as a Graph: Measurements, Models, and Methods
Kleinberg, J. M., Kumar, R., Raghavan, P., Rajagopalan, S., & Tomkins, A. S. (1999) · Lecture Notes in Computer Science · doi:10.1007/3-540-48686-0_1 · Cited by 1,016
(2003) · doi:10.5555/644108.644113 · Cited by 762
Automatic resource compilation by analyzing hyperlink structure and associated text
Chakrabarti, S., Dom, B., Raghavan, P., Rajagopalan, S., Gibson, D., & Kleinberg, J. (1998) · Computer Networks and ISDN Systems · doi:10.1016/s0169-7552(98)00087-7 · Cited by 697
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 Intelligent surfer: Probabilistic Combination of Link and Content Information in PageRank
Richardson, M., & Domingos, P. (2001) · Cited by 356
The Second Eigenvalue of the Google Matrix
Haveliwala, T. H., & Kamvar, S. D. (2003) · Cited by 310
Self-citation(1999) · Cited by 293
PageRank Computation and the Structure of the Web: Experiments and Algorithms
Arasu, A., Novak, J., Tomkins, A., & Tomlin, J. A. (2002) · Cited by 202
WebBase: a repository of Web pages
Hirai, J., Raghavan, S., Garcia-Molina, H., & Paepcke, A. (2000) · Computer Networks · doi:10.1016/s1389-1286(00)00063-3 · Cited by 183
The structure of broad topics on the web
Chakrabarti, S., Joshi, M. M., Punera, K., & Pennock, D. M. (2002) · International World Wide Web Conference (WWW) · doi:10.1145/511446.511480 · Cited by 129
What is this page known for? Computing Web page reputations
Rafiei, D., & Mendelzon, A. O. (2000) · Computer Networks · doi:10.1016/s1389-1286(00)00078-5 · Cited by 126
Numerical Solution of Large Finite Markov Chains by Algebraic Multigrid Techniques
Krieger, U. R. (1995) · Springer eBooks · doi:10.1007/978-1-4615-2241-6_23 · Cited by 34
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
Topic-sensitive pagerank: A context-sensitive ranking algorithm for web search
Haveliwala, T. H. (2003) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2003.1208999 · Cited by 1,052
Self-citationLangville, A., & Meyer, C. (2004) · Internet Mathematics · doi:10.1080/15427951.2004.10129091 · Cited by 894
Co-authorship networks in the digital library research community
Liu, X., Bollen, J., Nelson, M. L., & Van de Sompel, H. (2005) · Information Processing & Management · doi:10.1016/j.ipm.2005.03.012 · Cited by 823
(2003) · doi:10.5555/644108.644113 · Cited by 762
Metadata
- Authors
- Kamvar, S. D., Haveliwala, T. H., Manning, C. D., & Golub, G. H.
- Venue
- Proceedings of the twelfth international conference on World Wide Web - WWW '03
- Publisher
- ACM Press
- Published
- 2003
- Pages
- 261
- OpenAlex
- W2161118554
- Cited by
- 407
- References
- 20
- Type
- conference abstract
- Language
- en
- Open access
- closed
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.