The DOI matches its Crossref record; 30 of the 30 references it cites were found in a registry or an index.
Convergence Analysis of a PageRank Updating Algorithm by Langville and Meyer
Abstract
The PageRank updating algorithm proposed by Langville and Meyer is a special case of an iterative aggregation/disaggregation (SIAD) method for computing stationary distributions of very large Markov chains. It is designed, in particular, to speed up the determination of PageRank, which is used by the search engine Google in the ranking of web pages. In this paper the convergence, in exact arithmetic, of the SIAD method is analyzed. The SIAD method is expressed as the power method preconditioned by a partial LU factorization. This leads to a simple derivation of the asymptotic convergence rate of the SIAD method. It is known that the power method applied to the Google matrix always converges, and we show that the asymptotic convergence rate of the SIAD method is at least as good as that of the power method. Furthermore, by exploiting the hyperlink structure of the web it can be shown that the asymptotic convergence rate of the SIAD method applied to the Google matrix can be made strictly faster than that of the power method.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Citations
Cites
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
(1999) · Cited by 12,854
Varga, R. S. (2000) · Springer Series in Computational Mathematics · doi:10.1007/978-3-642-05156-2 · Cited by 5,811
Nonnegative Matrices in the Mathematical Sciences
(1979) · Elsevier eBooks · doi:10.1016/c2013-0-10361-3 · Cited by 5,451
Bramble, J. H., & Varga, R. S. (1963) · Mathematics of Computation · doi:10.2307/2003862 · Cited by 4,091
Nonnegative Matrices in the Mathematical Sciences
Berman, A., & Plemmons, R. J. (1994) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611971262 · Cited by 3,573
Non-negative Matrices and Markov Chains
Seneta, E. (1981) · Springer Series in Statistics · doi:10.1007/0-387-32792-4 · Cited by 2,807
Introduction to the Numerical Solution of Markov Chains
Stewart, W. J. (1995) · Princeton University Press eBooks · doi:10.1515/9780691223384 · Cited by 1,750
Numerical Computing with Matlab
Moler, C. B. (2004) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9780898717952 · Cited by 646
Extrapolation methods for accelerating PageRank computations
Kamvar, S. D., Haveliwala, T. H., Manning, C. D., & Golub, G. H. (2003) · Proceedings of the twelfth international conference on World Wide Web - WWW '03 · doi:10.1145/775152.775190 · Cited by 407
Cited by
Efficient Global 2D-3D Matching for Camera Localization in a Large-Scale 3D Map
Liu, L., Li, H., & Dai, Y. (2017) · 2017 IEEE International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2017.260 · Cited by 165
A classification and review of timed Markov models of manufacturing systems
Papadopoulos, C. T., Li, J., & O’Kelly, M. E. J. (2018) · Computers & Industrial Engineering · doi:10.1016/j.cie.2018.12.019 · Cited by 116
The Effect of New Links on Google PageRank
Litvak, N., & Avrachenkov, K. E. (2004) · HAL · Cited by 113
An Arnoldi-type algorithm for computing page rank
Golub, G. H., & Greif, C. (2006) · BIT Numerical Mathematics · doi:10.1007/s10543-006-0091-y · Cited by 109
Ergodicity Coefficients Defined by Vector Norms
Ipsen, I. C. F., & Selee, T. M. (2011) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/090752948 · Cited by 104
Self-citation
Metadata
- Authors
- Ipsen, I. C. F., & Kirkland, S.
- Venue
- SIAM Journal on Matrix Analysis and Applications
- Published
- 2006-01
- Volume
- 27
- Issue
- 4
- Pages
- 952-967
- ISSN
- 0895-4798 (ISSN-L)
- 1095-7162
- OpenAlex
- W2166593446
- Cited by
- 60
- References
- 30
- Citations by year
- 2025: 1 · 2024: 1 · 2021: 1 · 2020: 1 · 2019: 1 · 2018: 3 · 2017: 4 · 2016: 1 · 2015: 3 · 2014: 2 · 2013: 4 · 2012: 7
- FWCI
- 7.70
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- SIAM Journal on Matrix Analysis and Applications (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Matrix Theory and Algorithms
- Physical Sciences › Computer Science › Information Systems › Information Retrieval and Search Behavior
- Physical Sciences › Computer Science › Information Systems › Web visibility and informetrics
- Keywords
- PageRank, convergence analysis, asymptotic convergence rate, power method, stationary distribution, Markov chains, Google matrix, web page ranking, hyperlink structure
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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Convergence Analysis of a PageRank Updating Algorithm by Langville and Meyer. https://app.cochat.ai/papers/10.1137/s0895479804439808
- The paper
- Ipsen, I. C. F., & Kirkland, S. (2006). Convergence Analysis of a PageRank Updating Algorithm by Langville and Meyer. SIAM Journal on Matrix Analysis and Applications. https://doi.org/10.1137/s0895479804439808
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.