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

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

Research output: Book/ReportReportProfessional

65 Downloads (Pure)

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.
Original languageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
ISBN (Print)0169-2690
Publication statusPublished - 2005

Publication series

Namememorandum
PublisherDepartment 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

Avrachenkov, K., Litvak, N., Nemirovsky, D., & Osipova, N. (2005). Monte Carlo methods in PageRank computation: When one iteration is sufficient. (memorandum; No. 1754). Enschede: University of Twente, Department of Applied Mathematics.
Avrachenkov, K. ; Litvak, Nelli ; Nemirovsky, D. ; Osipova, N. / Monte Carlo methods in PageRank computation: When one iteration is sufficient. Enschede : University of Twente, Department of Applied Mathematics, 2005. (memorandum; 1754).
@book{92a2b83a5bb04974b99e653828091954,
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 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.",
keywords = "MSC-62F25, MSC-68U35, MSC-60J22, IR-65938, EWI-3574, METIS-223976, MSC-65C05",
author = "K. Avrachenkov and Nelli Litvak and D. Nemirovsky and N. Osipova",
note = "Imported from MEMORANDA",
year = "2005",
language = "Undefined",
isbn = "0169-2690",
series = "memorandum",
publisher = "University of Twente, Department of Applied Mathematics",
number = "1754",

}

Avrachenkov, K, Litvak, N, Nemirovsky, D & Osipova, N 2005, 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.

Enschede : University of Twente, Department of Applied Mathematics, 2005. (memorandum; No. 1754).

Research output: Book/ReportReportProfessional

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 -

Avrachenkov K, Litvak N, Nemirovsky D, Osipova N. Monte Carlo methods in PageRank computation: When one iteration is sufficient. Enschede: University of Twente, Department of Applied Mathematics, 2005. (memorandum; 1754).