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

K. Avrachenkov, Nelli Litvak, D. Nemirovsky, N. Osipova

Research output: Contribution to journalArticleAcademicpeer-review

114 Citations (Scopus)

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 languageUndefined
Article number10.1137/050643799
Pages (from-to)890-904
Number of pages15
JournalSIAM journal on numerical analysis
Volume45
Issue numberLNCS4549/2
DOIs
Publication statusPublished - May 2007

Keywords

  • MSC-69J10
  • MSC-65C05
  • MSC-60J20
  • EWI-11058
  • IR-61917
  • METIS-241911

Cite this

Avrachenkov, K., Litvak, N., Nemirovsky, D., & Osipova, N. (2007). Monte Carlo methods in PageRank computation: When one iteration is sufficient. SIAM journal on numerical analysis, 45(LNCS4549/2), 890-904. [10.1137/050643799]. https://doi.org/10.1137/050643799
Avrachenkov, K. ; Litvak, Nelli ; Nemirovsky, D. ; Osipova, N. / Monte Carlo methods in PageRank computation: When one iteration is sufficient. In: SIAM journal on numerical analysis. 2007 ; Vol. 45, No. LNCS4549/2. pp. 890-904.
@article{5c5ae6cc00c14f14910705dcb8f7dd27,
title = "Monte Carlo methods in PageRank computation: When one iteration is sufficient",
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.",
keywords = "MSC-69J10, MSC-65C05, MSC-60J20, EWI-11058, IR-61917, METIS-241911",
author = "K. Avrachenkov and Nelli Litvak and D. Nemirovsky and N. Osipova",
note = "10.1137/050643799",
year = "2007",
month = "5",
doi = "10.1137/050643799",
language = "Undefined",
volume = "45",
pages = "890--904",
journal = "SIAM journal on numerical analysis",
issn = "0036-1429",
publisher = "Society for Industrial and Applied Mathematics",
number = "LNCS4549/2",

}

Avrachenkov, K, Litvak, N, Nemirovsky, D & Osipova, N 2007, 'Monte Carlo methods in PageRank computation: When one iteration is sufficient' SIAM journal on numerical analysis, vol. 45, no. LNCS4549/2, 10.1137/050643799, pp. 890-904. https://doi.org/10.1137/050643799

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

In: SIAM journal on numerical analysis, Vol. 45, No. LNCS4549/2, 10.1137/050643799, 05.2007, p. 890-904.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

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 - 10.1137/050643799

PY - 2007/5

Y1 - 2007/5

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

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

KW - MSC-69J10

KW - MSC-65C05

KW - MSC-60J20

KW - EWI-11058

KW - IR-61917

KW - METIS-241911

U2 - 10.1137/050643799

DO - 10.1137/050643799

M3 - Article

VL - 45

SP - 890

EP - 904

JO - SIAM journal on numerical analysis

JF - SIAM journal on numerical analysis

SN - 0036-1429

IS - LNCS4549/2

M1 - 10.1137/050643799

ER -