CoChat

Asymptotic analysis for personalized Web search

Open access
Volkovich, Yana, Litvak, Nelly · 2010 · Advances in Applied Probability

The DOI matches its Crossref record; 51 of the 51 references it cites were found in a registry or an index; 2 of the 18 sources its claims cite were checked for support.

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

Overview

CoChat Summary

## TL;DR

This paper models personalized PageRank as the solution to a stochastic fixed-point equation and derives its tail asymptotics under heavy-tailed in-degree and/or teleportation distributions. The main conclusion is that the PageRank tail is governed by the heaviest tail among the in-degree and teleportation, while out-degree has only a negligible effect.

## Key findings

  • The paper proves that the stochastic equation for PageRank has a unique nontrivial solution with mean 1.
  • Theorem 4.1 shows that the tail behavior of PageRank is determined by the heavier-tailed of the in-degree \(N\) and teleportation \(B\):
  • if \(P(B>x)=o(P(N>x))\), then PageRank follows the in-degree tail;
  • if \(P(N>x)=o(P(B>x))\), then PageRank follows the teleportation tail;
  • if \(P(B>x)\sim C_{BN}P(N>x)\), then both contribute.
  • In the numerical example on the Stanford data set, the authors use \(w=281{,}903\) pages and \(2{,}312{,}497\) links, with in-degree exponent \(\alpha_N=1.1\), and test teleportation exponents \(\alpha_B=0.5, 1.1, 3.0\).
  • For the Stanford sample, they report predicted PageRank log-log lines such as \(y=-1.1x-0.46\) for \(c=0.85\) and \(y=-1.1x-1.04\) for \(c=0.5\), and state that these match the experimental PageRank slopes well.

## Methods

  • The paper models personalized PageRank as a distributional fixed-point equation of the form \(R \overset{d}{=} \sum_{i=1}^N A_i R_i + B\), with \(N\) for in-degree and \(B\) for user preference/teleportation; it also analyzes the PageRank iteration via a Galton–Watson tree representation.
  • Tail asymptotics are derived using regular variation, Laplace–Stieltjes transform analysis, and a Tauberian theorem; the authors also analyze finite iterations and then pass to the limit.
  • Numerical experiments use the Stanford Web data set (\(281{,}903\) pages, \(2{,}312{,}497\) links) and matrix power iteration to compute personalized PageRank under different teleportation power laws.

## Limitations

  • The paper states that the assumption of a branching structure for the Web “is probably not justified.”
  • The authors note that the model/data differences depend on many factors, “in particular, on the choice of data set,” and that this affects the fit.
  • Evident from the text: several derivations require strong assumptions such as heavy-tailed regular variation, moment conditions, and noninteger \(\alpha=\min(\alpha_N,\alpha_B)>1\) in the Laplace-transform analysis.

Model-written summary. Check it against the paper before relying on it.

Integrity signals

Registry

Crossref · 10.1239/aap/1275055243

Cites

51 of 51 references verified0 citation errors · 0 not checkable

Statistics

Nothing to recompute.

Figures

Figure 1 An example of a Galton-Watson tree.
Figure 1 An example of a Galton-Watson tree.From the PDF
Figure 2 The k th iteration.
Figure 2 The k th iteration.From the PDF
Figure 3 Number of pages with in-degree/teleportation/PageRank greater than the values on the x -axes, on a log-log scale.
Figure 3 Number of pages with in-degree/teleportation/PageRank greater than the values on the x -axes, on a log-log scale.From the PDF

Verification

Claims the paper makes

1 Valid · 2 Not valid · 10 Not checked · 48 Own results and interpretations

25 more claims

Create a free account to see all 61 claims and to verify the 8 references still open.

See all claims — free account
  • Probably not a substantial claim. 17
  • It may state two separate claims as one. 14
  • The quote only partly states this claim. 1

Create a free account to see these claims.

Citations

Cites

Research works printed but not linked: 3

  1. [21] Kamvar, S. D., Haveliwala, T. H., Manning, C. D. and Golub, G. H. (2003). Exploiting the block structure of the Web for computing. Tech. Rep., Stanford University. -
  2. [6] Bingham, N. H., Goldie, C. M. and Teugels, J. L. (1989). Regular Variation . Cambridge University Press. -
  3. 10.1017/s0001867800008090 · doi:10.1017/s0001867800008090

Cited by

See all 69

Metadata

Authors
Volkovich, Y., & Litvak, N.
Affiliations
University of Twente (NL)
Corresponding author
  • Volkovich, Yana
  • Litvak, Nelly
Venue
Advances in Applied Probability
Published
2010-06
Volume
42
Issue
2
Pages
577-604
ISSN
  • 0001-8678 (ISSN-L)
  • 1475-6064
OpenAlex
W2109819452
Cited by
69
References
46
Citations by year
2026: 1 · 2025: 3 · 2024: 4 · 2023: 3 · 2022: 5 · 2021: 2 · 2020: 3 · 2019: 8 · 2018: 3 · 2017: 5 · 2016: 2 · 2015: 7 · 2014: 5 · 2013: 2 · 2012: 7
FWCI
14.35
Type
journal article
Language
en
Open access
Locations
  • Advances in Applied Probability (publishedVersion)
  • University of Twente Research Information (publishedVersion)
  • Project Euclid (Cornell University) (submittedVersion)
  • University of Twente Research Information (submittedVersion, other-oa)
  • University of Twente Research Information (submittedVersion)
Funders
Nederlandse Organisatie voor Wetenschappelijk Onderzoek
Topics
  • Physical Sciences › Computer Science › Information Systems › Information Retrieval and Search Behavior
  • Physical Sciences › Physics and Astronomy › Statistical and Nonlinear Physics › Complex Network Analysis Techniques
  • Social Sciences › Decision Sciences › Management Science and Operations Research › Probability and Risk Models
Keywords
personalized PageRank, web search, heavy-tailed distributions, power-law networks, regular variation, stochastic equations, user preferences, complex networks

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

The claim verdicts this report counts are experimental: their accuracy is not yet measured.

A language model drew the claims from the paper on 2026-10-10, under version 3 of the claim definition (model deepseek-v4.1-flash, prompt extract-v3).

A second model labelled each claim on 2026-10-10 (model jev-1.13-20260917, definition revision gold-guideline-v0.2).

Cited sources are checked with a language model’s help (qwen3.8-omni-flash).

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.