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

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

Research output: Book/ReportReportProfessional

78 Downloads (Pure)

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 provide good estimation of the PageRank for relatively important pages already after one iteration; Monte Carlo methods have natural parallel implementation; and finally, Monte Carlo methods allow to perform continuous update of the PageRank as the structure of the Web changes.
Original languageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
ISBN (Print)0169-2690
Publication statusPublished - 2005

Publication series

Namememorandum
PublisherDepartment of Applied Mathematics, University of Twente
No.1754
ISSN (Print)0169-2690

Keywords

  • MSC-62F25
  • MSC-68U35
  • MSC-60J22
  • IR-65938
  • EWI-3574
  • METIS-223976
  • MSC-65C05

Cite this

Avrachenkov, K., Litvak, N., Nemirovsky, D., & Osipova, N. (2005). Monte Carlo methods in PageRank computation: When one iteration is sufficient. (memorandum; No. 1754). Enschede: University of Twente, Department of Applied Mathematics.