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

Share/Save/Bookmark

Avrachenkov, K. and Litvak, N. and Nemirovsky, D. and Osipova, N. (2005) Monte Carlo methods in PageRank computation: When one iteration is sufficient. [Report]

open access
[img]
Preview
PDF
268kB
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.
Item Type:Report
Additional information:Imported from MEMORANDA
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/65938
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 223976