# Asymptotic analysis for personalized web search

Y. Volkovich, Nelli Litvak

30 Citations (Scopus)

### 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 language Undefined 577-604 28 Advances in applied probability 42 2 https://doi.org/10.1239/aap/1275055243 Published - 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.

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 -