### Abstract

Original language | Undefined |
---|---|

Place of Publication | Enschede |

Publisher | University of Twente, Department of Applied Mathematics |

ISBN (Print) | 0169-2690 |

Publication status | Published - 2005 |

### Publication series

Name | memorandum |
---|---|

Publisher | Department 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

*Monte Carlo methods in PageRank computation: When one iteration is sufficient*. (memorandum; No. 1754). Enschede: University of Twente, Department of Applied Mathematics.

}

*Monte Carlo methods in PageRank computation: When one iteration is sufficient*. memorandum, no. 1754, University of Twente, Department of Applied Mathematics, Enschede.

**Monte Carlo methods in PageRank computation: When one iteration is sufficient.** / Avrachenkov, K.; Litvak, Nelli; Nemirovsky, D.; Osipova, N.

Research output: Book/Report › Report › Professional

TY - BOOK

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

AU - Avrachenkov, K.

AU - Litvak, Nelli

AU - Nemirovsky, D.

AU - Osipova, N.

N1 - Imported from MEMORANDA

PY - 2005

Y1 - 2005

N2 - 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.

AB - 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.

KW - MSC-62F25

KW - MSC-68U35

KW - MSC-60J22

KW - IR-65938

KW - EWI-3574

KW - METIS-223976

KW - MSC-65C05

M3 - Report

SN - 0169-2690

T3 - memorandum

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

PB - University of Twente, Department of Applied Mathematics

CY - Enschede

ER -