Asymptotic analysis for personalized Web search

Yana Volkovich, Nelly Litvak

Research output: Book/ReportReportProfessional

44 Downloads (Pure)

Abstract

Personalized PageRank 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\stackrel{d}{=}\sum_{i=1}^NA_iR_i+B$, where $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 of 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 a good agreement with experimental data.
Original languageEnglish
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Number of pages30
Publication statusPublished - Oct 2008

Publication series

Name
PublisherDepartment of Applied Mathematics, University of Twente
No.1884
ISSN (Print)1874-4850

Keywords

  • MSC-68P10
  • MSC-40E05
  • MSC-90B15

Fingerprint

Dive into the research topics of 'Asymptotic analysis for personalized Web search'. Together they form a unique fingerprint.

Cite this