The DOI matches its Crossref record; 17 of the 17 references it cites were found in a registry or an index; none of the 12 sources its claims cite is checked for support yet.
Monte Carlo Methods in PageRank Computation: When One Iteration is Sufficient
Abstract
PageRank is one of the principle criteria according to which Google ranks Web pages. PageRank can be interpreted as a frequency of visiting a Web page by a random surfer, and thus it reflects the popularity of a Web page. Google computes the PageRank using the power iteration method, which requires about one week of intensive computations. In the present work we propose and analyze Monte Carlo‐type methods for the PageRank computation. There are several advantages of the probabilistic Monte Carlo methods over the deterministic power iteration method: Monte Carlo methods already provide good estimation of the PageRank for relatively important pages after one iteration; Monte Carlo methods have natural parallel implementation; and finally, Monte Carlo methods allow one to perform continuous update of the PageRank as the structure of the Web changes.
Overview
CoChat Summary
TL;DR
The paper proposes and analyzes Monte Carlo methods for PageRank computation, including a complete-path algorithm that records all visited pages and stops at dangling nodes. It shows theoretically and experimentally that important pages can be estimated accurately after one iteration, with cyclic-start Monte Carlo outperforming random-start Monte Carlo and complete-path stopping at dangling nodes performing best on their dataset.
Key findings
- MC complete path stopping at dangling nodes gives small error for important pages already after the first iteration; on the INRIA dataset it outperforms power iteration even for the first 1000 most important pages. One iteration gave a relative error of only 7% with 95% confidence for pages with high PageRank, and if important pages have PageRank 10^4 times larger than the minimal PageRank value, the method achieves about 1% error for important pages after the first iteration.
- MC algorithms with cyclic start outperform MC algorithms with random start. On the dataset, MC complete path stopping at dangling nodes performs best, followed by MC complete path with random start; MC end-point with cyclic start has the worst performance.
- The number of required samples is linear in n, and a reasonable evaluation for popular pages can be obtained even with N = n, i.e., one run per page; this is much less pessimistic than the earlier rough O(n^2) estimate. The estimator is consistent, and the additional relative error from estimating γ is of order 1/√(mn) and can essentially be neglected.
- The PageRank vector on the dataset follows a power law closely.
Methods
- Design: theoretical analysis of Monte Carlo PageRank algorithms based on the absorbing Markov chain interpretation, with convergence and confidence-interval comparisons; algorithms include MC end-point with random start, MC end-point with cyclic start, MC complete path, MC complete path stopping at dangling nodes, and MC complete path with random start.
- Data: the Web site of INRIA Sophia Antipolis, about 50000 Web pages and 200000 hyperlinks; data collected with a custom Web crawler using an Oracle database, and power iteration plus three MC algorithms implemented in PL/SQL.
- Main analysis: computed PageRank with 20 digits accuracy via sufficient power iterations, sorted the PageRank vector, chose four elements, performed 10 iterations of the PI method and 10 iterations of the three implemented MC algorithms, and compared actual relative error and 95% confidence intervals.
Limitations
- The paper states that if first-iteration results are unsatisfactory, increasing m is hard to improve: after m iterations the MC relative error reduces on average only by the factor 1/√m, whereas the power iteration error decreases exponentially with m; MC can still be advantageous because of simplicity in parallel implementation.
- The paper states that the choice between end-point and complete-path versions depends on the total PageRank of dangling nodes and the probability of a cycle returning to j; many short cycles add high extra variability, and high dangling-node rank can stop walks early, potentially making the difference negligible. On a modified graph including intra-page hyperlinks, the MC methods showed very slow convergence.
- Evident from the text: experiments use one Web site (about 50000 pages and 200000 hyperlinks), not the full Web, and the variance derivation assumes that all W_ij’s are independent.
Model-written summary. Check it against the paper before relying on it.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
0 Valid · 4 Not valid · 9 Not checked · 31 Own results and interpretations
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Monte Carlo methods provide good estimation of the PageRank for relatively important pages already after one iteration”
- Also stated in: § Proof. See the Appendix. · boosted
“Strikingly, it follows from (18) that the Monte Carlo method gives good results for important pages in one iteration only, that is, when m = 1.”
- Also stated in: § 5 Conclusions · boosted
“Our theoretical and experimental results have demonstrated that the Monte Carlo algorithms determine the PageRank of relatively important pages already after the first iteration.”
boostedstates a cause- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Also stated in: § Proof. See the Appendix. · boosted
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“One can show however that Algorithm 4 provides an estimator with a smaller variance than Algorithm 5.”
- Also stated in: § 2 Monte Carlo algorithms · plain
“Hence, Algorithm 4 provides random variables with smaller variance in both numerator and denominator of (11).”
plainstates a cause- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: unclear — It is unclear whether the paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Also stated in: § 2 Monte Carlo algorithms · plain
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Thus, ¯ W equals the number of dangling nodes n 0 plus the sum of n -n 0 independent random variables ˆ W i · , i ∈ I 1 .”
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Rests on an assumption not shown here.
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Second, Theorem 1 states that the error in the estimate of π j originates mainly from estimating w · j .”
plainstates a cause- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“The factor C ( β ) can be approximated as”
- Also stated in: § 3 Convergence Analysis · plain
“where x 1 -β/ 2 is a (1 -β/ 2) -quantile of the standard normal distribution and n 0 is the number of dangling nodes.”
plainstates an association- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Also stated in: § 3 Convergence Analysis · plain
21 more claims
Create a free account to see all 44 claims and every source verdict.
- Probably not a substantial claim. 11
- The quote only partly states this claim. 2
- It may state two separate claims as one. 7
Citations
Cites
(1999) · Cited by 12,854
Broder, A., Kumar, R., Maghoul, F., Raghavan, P., Rajagopalan, S., Stata, R., Tomkins, A., & Wiener, J. (2000) · Computer Networks · doi:10.1016/s1389-1286(00)00083-9 · Cited by 2,810
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
Langville, A., & Meyer, C. (2004) · Internet Mathematics · doi:10.1080/15427951.2004.10129091 · Cited by 894
Bianchini, M., Gori, M., & Scarselli, F. (2005) · ACM Transactions on Internet Technology · doi:10.1145/1052934.1052938 · Cited by 539
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
Challenges in web search engines
Henzinger, M. R., Motwani, R., & Silverstein, C. (2002) · ACM SIGIR Forum · doi:10.1145/792550.792553 · Cited by 307
Adaptive methods for the computation of PageRank
Kamvar, S., Haveliwala, T., & Golub, G. (2004) · Linear Algebra and its Applications · doi:10.1016/j.laa.2003.12.008 · Cited by 271
Adaptive on-line page importance computation
Abiteboul, S., Preda, M., & Cobena, G. (2003) · Proceedings of the twelfth international conference on World Wide Web - WWW '03 · doi:10.1145/775152.775192 · Cited by 213
Dill, S., Kumar, R., Mccurley, K. S., Rajagopalan, S., Sivakumar, D., & Tomkins, A. (2002) · ACM Transactions on Internet Technology · doi:10.1145/572326.572328 · Cited by 197
Towards Scaling Fully Personalized PageRank
Fogaras, D., & Rácz, B. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-30216-2_9 · Cited by 84 · cited 5×
“In particular, we propose an algorithm that takes into account the information not only about the last visited page (as in [3, 8]), but also about all pages visited during the simulation run.”
BackgroundMethodInfluentialAlgorithmic Challenges in Web Search Engines
Henzinger, M. R. (2004) · Internet Mathematics · doi:10.1080/15427951.2004.10129079 · Cited by 81
Updating pagerank with iterative aggregation
Langville, A. N., & Meyer, C. D. (2004) · Proceedings of the 13th international World Wide Web conference on Alternate track papers & posters - WWW Alt. '04 · doi:10.1145/1013367.1013491 · Cited by 64
Breyer, L. A., & Roberts, G. O. (2001) · Methodology And Computing In Applied Probability · doi:10.1023/a:1012205210377 · Cited by 25
Convergence analysis of an improved pagerank algorithm
Ipsen, I. C. F., & Kirkland, S. (2004) · NCSU Libraries Repository (North Carolina State University Libraries) · Cited by 14
Updating pagerank with iterative aggregation
Langville, A. N., & Meyer, C. D. (2004) · Alternate track papers & posters of the 13th international conference on World Wide Web - WWW Alt. '04 · doi:10.1145/1010432.1010556
Cited by
Fast incremental and personalized PageRank
Bahmani, B., Chowdhury, A., & Goel, A. (2010) · Proceedings of the VLDB Endowment · doi:10.14778/1929861.1929864 · Cited by 327
“Our algorithm is a Monte Carlo method [2] that works by maintaining a small number of short random walk segments starting at each node in the social graph.”
BackgroundMethodInfluentialk-nearest neighbors in uncertain graphs
Potamias, M., Bonchi, F., Gionis, A., & Kollios, G. (2010) · Proceedings of the VLDB Endowment · doi:10.14778/1920841.1920967 · Cited by 235
Heat kernel based community detection
Kloster, K., & Gleich, D. F. (2014) · Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2623330.2623706 · Cited by 205
“[13] to achieve a randomized sublinear time algorithm to estimate the largest PageRank entries, and in fact, Monto Carlo methods frequently feature in PageRank computations due to the relationship between the diffusion and a random walk [7, 13, 8, 9].”
MethodScalable Graph Embedding for Asymmetric Proximity
Zhou, C., Liu, Y., Liu, X., Liu, Z., & Gao, J. (2017) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v31i1.10878 · Cited by 190
“Due to the complexity of the iteration-style computation, Monte Carlo approach is usually adopted when calculating Rooted PageRank values (Gupta et al. 2013; Fogaras et al. 2005; Bahmani, Chowdhury, and Goel 2010; Avrachenkov et al. 2007).”
MethodAn Introduction to Search Engines and Web Navigation
Levene, M. (2010) · Wiley eBooks · doi:10.1002/9780470874233 · Cited by 197
Metadata
- Authors
- Avrachenkov, K., Litvak, N., Nemirovsky, D., & Osipova, N.
- Affiliations
- Institut national de recherche en sciences et technologies du numérique (FR)
- Venue
- SIAM Journal on Numerical Analysis
- Published
- 2007-01
- Volume
- 45
- Issue
- 2
- Pages
- 890-904
- ISSN
- 0036-1429 (ISSN-L)
- 1095-7170
- OpenAlex
- W2107577105
- Cited by
- 250
- References
- 15
- Citations by year
- 2026: 2 · 2025: 5 · 2024: 15 · 2023: 13 · 2022: 15 · 2021: 10 · 2020: 13 · 2019: 20 · 2018: 10 · 2017: 14 · 2016: 17 · 2015: 19 · 2014: 27 · 2013: 18 · 2012: 11
- FWCI
- 12.08
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- SIAM Journal on Numerical Analysis (publishedVersion)
- University of Twente Research Information (publishedVersion)
- University of Twente Research Information (submittedVersion)
- 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 › Mathematics › Statistics and Probability › Markov Chains and Monte Carlo Methods
- Keywords
- PageRank, Monte Carlo methods, power iteration, web page ranking, parallel computing
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.
A language model drew the claims from the paper on 2026-10-10, under version 3 of the claim definition (model deepseek-v4.1-flash, prompt extract-v3).
A second model labelled each claim on 2026-10-10 (model jev-1.13-20260917, definition revision gold-guideline-v0.2).
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.