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 language | Undefined |
---|---|
Article number | 10.1137/050643799 |
Pages (from-to) | 890-904 |
Number of pages | 15 |
Journal | SIAM journal on numerical analysis |
Volume | 45 |
Issue number | LNCS4549/2 |
DOIs | |
Publication status | Published - May 2007 |
Keywords
- MSC-69J10
- MSC-65C05
- MSC-60J20
- EWI-11058
- IR-61917
- METIS-241911