Monte Carlo methods in PageRank computation: When one iteration is sufficient

K. Avrachenkov, Nelli Litvak, D. Nemirovsky, N. Osipova

Research output: Contribution to journalArticleAcademicpeer-review

159 Citations (Scopus)

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.
Original languageUndefined
Article number10.1137/050643799
Pages (from-to)890-904
Number of pages15
JournalSIAM journal on numerical analysis
Volume45
Issue numberLNCS4549/2
DOIs
Publication statusPublished - May 2007

Keywords

  • MSC-69J10
  • MSC-65C05
  • MSC-60J20
  • EWI-11058
  • IR-61917
  • METIS-241911

Cite this