Student or educator? Sign up with your school email and get 6 months of Pro free.
CoChat

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

Avrachenkov, K., Litvak, N., Nemirovsky, D., Osipova, N. · 2007 · SIAM Journal on Numerical Analysis

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

Crossref · 10.1137/050643799

Cites

17 of 17 references verified0 citation errors · 0 not checkable

Statistics

Nothing to recompute.

Verification

Claims the paper makes

0 Valid · 4 Not valid · 9 Not checked · 31 Own results and interpretations

21 more claims

Create a free account to see all 44 claims and every source verdict.

See all claims — free account
  • Probably not a substantial claim. 11
  • The quote only partly states this claim. 2
  • It may state two separate claims as one. 7

Create a free account to see these claims.

Citations

Cites

Cited by

See all 254

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.