Monte Carlo Methods in PageRank Computation: When One Iteration is Sufficient
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.
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
Figures
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 · cited 1×
“According to [6, 14], the ratio between the number of links and number of pages of the Web is between 7.”
BackgroundScaling 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 · cited 2×
“The end-point of a random walk that starts from a random page and can be terminated at each step with probability 1 − c, appears to be a sample from the distribution π [4, 7, 9].”
BackgroundThe 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 · cited 2×
“For instance, in [2], the PageRank is seen as the average number of surfers navigating a given page at a given time instant provided that at each time instant t ≥ 0, a surfer can cease from navigating with probability (1 − c) and on average (1 − c) surfers start navigating from each page.”
BackgroundExtrapolation 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
Cited by
Items 201–254 of 254
Hearsay: Suppressing spam using trust in mobile social gossiping networks
Steenbergen, O. (2012) · Research Repository (Delft University of Technology) · Cited by 1
Multiplicative Approximations of Random Walk Transition Probabilities
Kapralov, M., & Panigrahy, R. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-22935-0_23 · Cited by 1
“S = Ω̃(sn2/d) space, then the threshold t is exponentially small in the length of the walk l and even very small transition probabilities can be approximated up to a 1± factor.”
BackgroundA Random Walk based Trust Ranking in Distributed SystemsPreprint
Stannat, A., & Pouwelse, J. A. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1903.05900 · Cited by 1
Distributed Randomized Algorithms for the PageRank ComputationPreprint
Ishii, H., & Tempo, R. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1203.6599 · Cited by 1
“That is, each page exchanges its value with the pages that it is linked to and those linked to it.”
BackgroundEfficient PageRank Computation via Distributed Algorithms with Web ClusteringPreprint
Suzuki, A., & Ishii, H. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1907.09979 · Cited by 1
“, [2]) and distributed algorithms (e.”
Benotman, H. (2020) · doi:10.15760/etd.7299 · Cited by 1
Large-scale Sustainable Search on Unconventional Computing HardwarePreprint
Kalinin, K. P., & Berloff, N. G. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2104.02553 · Cited by 4
Kundu, S., & Pashikanti, R. P. (2022) · Research Square · doi:10.21203/rs.3.rs-1512145/v1 · Cited by 1
Laplacian Powers for Graph-Based Semi-Supervised Learning
Bautista, E. (2019) · theses.fr (ABES) · doi:10.70675/3544ca3ez14c1z4750z82eaz781dc4646030 · Cited by 2
The power of locality in network algorithms
Brautbar, M. (2013)
MCHITS: Monte Carlo based Method for Hyperlink Induced Topic Search on Networks
Jin, Z., Shi, D., Wu, Q., et al. (2013) · Journal of Networks · doi:10.4304/jnw.8.10.2376-2382
“In order to compute the stable probability of each node, either power iteration of linear algebra [1] or Monte Carlo method [7, 8] can be used.”
MethodLeverage the BinRank's performance using HubRank and Parallel Computing
Dayananda, P., & Thnga Selvi, A. (2012)
Generating Msg's by Binrank for Scaling in Dynamic Authority Based Search
Pinapatruni, S. L., & Somayajula, S. P. K. (2011)
A Stochastic System Model for PageRank: Parameter Estimation and Adaptive Control
Clifton, C. E. (2015) · KU ScholarWorks (University of Kansas)
Understanding preferences and similarities from user-authored text
Ganu, G. (2014) · doi:10.7282/t3pr7t3t
“The second approach to compute PageRank is base d on Monte Carlo approximation which has the benefit of being very efficient and highly sca lable [11].”
MethodRandom walks in distributed networks and their applications
Anisur, R. M. (2014) · doi:10.32657/10356/58914
“We present a Monte Carlo based distributed algorithm for computing PageRank vector of a network [10].”
BackgroundMethodInfluentialRandom Walk Based Key Nodes Discovery in Opportunistic Networks
Qin, Q., & He, Y. (2016) · International Journal of Online and Biomedical Engineering (iJOE) · doi:10.3991/ijoe.v12i03.5412
An Efficient Monte Carlo Approach to Compute PageRank for Large Graphs on a Single PC
Sonobe, T. (2016) · Foundations of Computing and Decision Sciences · doi:10.1515/fcds-2016-0002
“The other way is Monte Carlo method [1].”
MethodInfluentialCapabilities and Expertise Required for Data Scientists in the Age of Big Data
Ishikawa, H. (2015) · CRC Press eBooks · doi:10.1201/b18223-16
Recursive Parameter Estimation
Chen, H.-F., & Zhao, W. (2014) · CRC Press eBooks · doi:10.1201/b17078-6
User Behavior Mining in Microblogging
Hoang, T. A. (2016) · Singapore Management University Institutional Knowledge (InK) (Singapore Management University)
A Probability PPV Model for Social Network Influence Maximization Problem
Ge, Y., & Wang, D. (2016) · doi:10.2991/aiie-16.2016.9
Towards fast algorithms for estimating Personalized PageRank using commonly generated random walks
Vial, D., & Subramanian, V. (2016) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2016.7852322
“This interpretation leads to an equivalent definition of PPR (1), which suggests Monte Carlo sampling of PPR is possible ([2],[3],[10]).”
BackgroundScalable Approaches for Recommendation in Social Networks
Li, Y. (2015) · HAL
Strongly connected components based efficient computation of page rank
Yang, H., Shen, D., Kou, Y., et al. (2017) · Frontiers of Computer Science · doi:10.1007/s11704-016-6168-0
Ghanbari, S., Heydari, H., & Moeini, A. (2017) · doi:10.1109/inista.2017.8001205
“Earlier works like [10] used Monte Carlo method to proposing of reducing number of iterations and determined PageRank after only one iteration with high accuracy.”
MethodEfficient Top-k Search for PageRank
Fujiwara, Y., Nakatsuji, M., Shiokawa, H., et al. (2015) · Transactions of the Japanese Society for Artificial Intelligence · doi:10.1527/tjsai.30.473
Closure Operators and Spam Resistance for PageRank.Preprint
Farach-Colton, L., Farach-Colton, M., Levi, R., et al. (2018) · arXiv (Cornell University)
An Intelligent Matching Algorithm of CDCI Model
Nan, Y., Liu, Y., & Chai, Y. (2018) · International Conference on Crowd Science and Engineering (ICCSE) · doi:10.1145/3265689.3265713
Virtual Web Based Personalized PageRank UpdatingPreprint
Song, B., Jiang, X., & Zhuang, X. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1901.00678
“in [3] and is testified experimentally by Ohsaka et al.”
BackgroundMethodVirtual web for PageRank computing
Song, B. (2018) · doi:10.32469/10355/66110
Reinforcement Learning for Matrix Computations: PageRank as an ExamplePreprint
Borkar, V. S., & Mathkar, A. S. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1311.2889
“While a bulk of the work in this direction has been on efficient computations for the power method, there have also been alternative approaches, such as Markov Chain Monte Carlo [17], [18], optimization based methods [19], and schemes based on stochastic approximation and/or gossip [20], [21], [22].”
MethodAn Uncertainty-Aware Approach for Exploratory Microblog RetrievalPreprint
Liu, M., Liu, S., Zhu, X., Liao, Q., Wei, F., & Pan, S. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1512.04038
“The advantages of this sampling method over the matrix-based method are as follows [2]: • Ranking scores are locally updated when the input changes locally; • The ranking scores of important items are accurately estimated after a few iterations; • The uncertainty of the ranking scores are modeled accurately because th…”
MethodTwo-Hop Walks Indicate PageRank OrderPreprint
Tang, Y. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1903.03756
“Much effort for accelerating the PageRank algorithm has been carried out from different view, such as Monte Carlo method [16], random walk [17], power method or general linear system [18, 19], graph theory [20, 21, 22], Schrödinger equation [23], and quantum networks [24, 25].”
MethodA Simple Study of Pleasing Parallelism on Multicore Computers
Ren, Y., & Gleich, D. F. (2020) · Modeling and simulation in science, engineering & technology · doi:10.1007/978-3-030-43736-7_11
“[Avrachenkov et al., 2007] K. Avrachenkov, N. Litvak, D. Nemirovsky, and N. Osipova.”
MethodEfficient and scalable techniques for pagerank-based graph analytics
Yang, R. (2020) · DR-NTU (Nanyang Technological University) · doi:10.32657/10356/145185
Suggesting Queries using Query-Flow Graphs to find Dutch Content with Curated Tags
Guijt, D. (2014) · Research Repository (Delft University of Technology)
(2010) · Wiley eBooks · doi:10.1002/9780470874233.biblio
Other Problems Reducible to Parameter Estimation
Chen, H.-F., & Zhao, W. (2014) · CRC Press eBooks · doi:10.1201/b17078-9
Scalability and Outlier Detection
Ishikawa, H. (2015) · CRC Press eBooks · doi:10.1201/b18223-15
Efficient optimization of network metrics in large uncertain graphs
Saha, A. (2022) · DR-NTU (Nanyang Technological University) · doi:10.32657/10356/163960
Two Parallel PageRank Algorithms via Improving Forward PushPreprint
Zhang, Q., Tang, R., Yao, Z., et al. (2023) · Research Square · doi:10.21203/rs.3.rs-2624542/v1
HedgeRank: Heterogeneity-Aware, Energy-Efficient Partitioning of Personalized PageRank at the Edge
Gong, Y. (2023) · Micromachines · doi:10.3390/mi14091714
“, software modifications [14,15] or hardware accelerators [9,19]), our HedgeRank exploits existing processing units (i.”
BackgroundApplication of an extrapolation method in the Hessenberg algorithm for computing PageRank
Hu, Q.-Y., Gu, X., & Wen, C. (2024) · The Journal of Supercomputing · doi:10.1007/s11227-024-06327-y
“…the inner and outer iteration [20], the adaptive method [21] gradually removes the converged web pages in the calculation process, lumping methods [22–24] lump the same type nodes to simple PageRank problem, Monte Carlo methods [25, 26] sample the transition matrix in PageRank computations.”
Study on the Webpage properties and prediction using Google.
Sadasivuni, S. T., & Sudarsan, S. (2024) · International Conference on Social and Sustainable Innovations in Technology and Engineering (SASI-ITE) · doi:10.1109/sasi-ite58663.2024.00066
Revisiting Local PageRank Estimation on Undirected Graphs: Simple and Optimal
Wang, H. (2024) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/3637528.3671820
Performance Comparison of Estimation Methods in Network Analysis
Pirouz, M. (2024) · IEEE Annual Ubiquitous Computing, Electronics & Mobile Communication Conference (UEMCON) · doi:10.1109/uemcon62879.2024.10754752
Beyond influence: voting theory for opinion maximization
Saha, A., Ke, X., Khan, A., & Lakshmanan, L. V. S. (2025) · The VLDB Journal · doi:10.1007/s00778-025-00933-9
Randomly sparsified Richardson iteration: A dimension‐independent sparse linear solver
Weare, J., & Webber, R. J. (2025) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.70012 · Cited by 2
“Alternative Monte Carlo algorithms such as [6, Alg.”
InfluentialScaling up Electrical Closeness Centrality Computation
Liao, M., Li, R.-H., Dai, Q., & Wang, G. (2026) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2026.3670233
Managing uncertainty through trust in resource sharing systems
Wang, N. (2020) · theses.fr (ABES) · doi:10.70675/917ca54az02fez4361zaf07z278af17fa874
Sankofa: Online Query-Adaptive Dynamic Graph Summaries
Bainson, A. B., Mortensen, K. O., Zaporojets, K., Mottin, D., & Karras, P. (2026) · Proceedings of the VLDB Endowment · doi:10.14778/3828612.3828641 · Cited by 1
“The classic PageRank algorithm computes an exact solution by matrix-algebra power iteration .”
Influential
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.



