Asymptotic analysis for personalized web search

Y. Volkovich, Nelli Litvak

Research output: Contribution to journalArticleAcademicpeer-review

28 Citations (Scopus)
63 Downloads (Pure)

Abstract

PageRank with personalization is used in Web search as an importance measure for Web documents. The goal of this paper is to characterize the tail behavior of the PageRank distribution in the Web and other complex networks characterized by power laws. To this end, we model the PageRank as a solution of a stochastic equation $R \buildrel\rm D\over= \sum^N_{i=1} A_i R_i + B$, where the $R_i$s are distributed as $R$. This equation is inspired by the original definition of the PageRank. In particular, $N$ models the number of incoming links to a page, and $B$ stays for the user preference. Assuming that $N$ or $B$ are heavy tailed, we employ the theory of regular variation to obtain the asymptotic behavior of $R$ under quite general assumptions on the involved random variables. Our theoretical predictions show good agreement with experimental data.
Original languageUndefined
Pages (from-to)577-604
Number of pages28
JournalAdvances in applied probability
Volume42
Issue number2
DOIs
Publication statusPublished - 2010

Keywords

  • MSC-68P10
  • MSC-90B15
  • MSC-40E05
  • PageRank
  • Stochastic equation
  • IR-72522
  • EWI-18088
  • Regular variation
  • Web
  • METIS-270886
  • Tauberian theorem

Cite this

@article{30b7a6a79783446d85157fc6b395d194,
title = "Asymptotic analysis for personalized web search",
abstract = "PageRank with personalization is used in Web search as an importance measure for Web documents. The goal of this paper is to characterize the tail behavior of the PageRank distribution in the Web and other complex networks characterized by power laws. To this end, we model the PageRank as a solution of a stochastic equation $R \buildrel\rm D\over= \sum^N_{i=1} A_i R_i + B$, where the $R_i$s are distributed as $R$. This equation is inspired by the original definition of the PageRank. In particular, $N$ models the number of incoming links to a page, and $B$ stays for the user preference. Assuming that $N$ or $B$ are heavy tailed, we employ the theory of regular variation to obtain the asymptotic behavior of $R$ under quite general assumptions on the involved random variables. Our theoretical predictions show good agreement with experimental data.",
keywords = "MSC-68P10, MSC-90B15, MSC-40E05, PageRank, Stochastic equation, IR-72522, EWI-18088, Regular variation, Web, METIS-270886, Tauberian theorem",
author = "Y. Volkovich and Nelli Litvak",
note = "10.1239/aap/1275055243",
year = "2010",
doi = "10.1239/aap/1275055243",
language = "Undefined",
volume = "42",
pages = "577--604",
journal = "Advances in applied probability",
issn = "0001-8678",
publisher = "University of Sheffield",
number = "2",

}

Asymptotic analysis for personalized web search. / Volkovich, Y.; Litvak, Nelli.

In: Advances in applied probability, Vol. 42, No. 2, 2010, p. 577-604.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Asymptotic analysis for personalized web search

AU - Volkovich, Y.

AU - Litvak, Nelli

N1 - 10.1239/aap/1275055243

PY - 2010

Y1 - 2010

N2 - PageRank with personalization is used in Web search as an importance measure for Web documents. The goal of this paper is to characterize the tail behavior of the PageRank distribution in the Web and other complex networks characterized by power laws. To this end, we model the PageRank as a solution of a stochastic equation $R \buildrel\rm D\over= \sum^N_{i=1} A_i R_i + B$, where the $R_i$s are distributed as $R$. This equation is inspired by the original definition of the PageRank. In particular, $N$ models the number of incoming links to a page, and $B$ stays for the user preference. Assuming that $N$ or $B$ are heavy tailed, we employ the theory of regular variation to obtain the asymptotic behavior of $R$ under quite general assumptions on the involved random variables. Our theoretical predictions show good agreement with experimental data.

AB - PageRank with personalization is used in Web search as an importance measure for Web documents. The goal of this paper is to characterize the tail behavior of the PageRank distribution in the Web and other complex networks characterized by power laws. To this end, we model the PageRank as a solution of a stochastic equation $R \buildrel\rm D\over= \sum^N_{i=1} A_i R_i + B$, where the $R_i$s are distributed as $R$. This equation is inspired by the original definition of the PageRank. In particular, $N$ models the number of incoming links to a page, and $B$ stays for the user preference. Assuming that $N$ or $B$ are heavy tailed, we employ the theory of regular variation to obtain the asymptotic behavior of $R$ under quite general assumptions on the involved random variables. Our theoretical predictions show good agreement with experimental data.

KW - MSC-68P10

KW - MSC-90B15

KW - MSC-40E05

KW - PageRank

KW - Stochastic equation

KW - IR-72522

KW - EWI-18088

KW - Regular variation

KW - Web

KW - METIS-270886

KW - Tauberian theorem

U2 - 10.1239/aap/1275055243

DO - 10.1239/aap/1275055243

M3 - Article

VL - 42

SP - 577

EP - 604

JO - Advances in applied probability

JF - Advances in applied probability

SN - 0001-8678

IS - 2

ER -