Monte Carlo methods of PageRank computation

Research output: Book/ReportReportProfessional

23 Downloads (Pure)

Abstract

We describe and analyze an on-line Monte Carlo method of PageRank computation. The PageRank is being estimated basing on results of a large number of short independent simulation runs initiated from each page that contains outgoing hyperlinks. The method does not require any storage of the hyperlink matrix and is highly parallelizable. We study confidence intervals, and discover drawbacks of the absolute error criterion and the relative error criterion. Further, we suggest a so-called weighted relative error criterion, which ensures a good accuracy in a relatively small number of simulation runs. Moreover, with the weighted relative error measure, the complexity of the algorithm does not depend on the web structure.
Original languageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Number of pages17
Publication statusPublished - 2004

Publication series

NameMemorandum Faculty of Mathematical Sciences
PublisherUniversity of Twente, Department of Applied Mathematics
No.1714
ISSN (Print)0169-2690

Keywords

  • MSC-62F25
  • MSC-68U35
  • MSC-60J20
  • IR-65899
  • MSC-65C05
  • METIS-217680
  • EWI-3534

Cite this