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

Avrachenkov, K. and Litvak, N. and Nemirovsky, D. and Osipova, N. (2007) Monte Carlo methods in PageRank computation: When one iteration is sufficient. SIAM Journal on Numerical Analysis, 45 (2). pp. 890-904. ISSN 0036-1429

PDF
Restricted to UT campus only: Request a copy
207Kb

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.
Item Type:	Article
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Stochastic Operations Research (SOR)
Link to this item:	http://purl.utwente.nl/publications/61917
Official URL:	http://dx.doi.org/10.1137/050643799
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 241911