Asymptotic analysis for personalized Web search
Open accessThe 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
Cites
Statistics
Figures
Verification
Claims the paper makes
1 Valid · 2 Not valid · 10 Not checked · 48 Own results and interpretations
The cited sources that could be checked couldn’t confirm or dispute this claim.
In the paper
“Moreover, since the corresponding moments of X and N always exist together [26], we use only moments of X”
What the sources say
- Could not verifycites [26] [26] Litvak, N., Scheinhardt, W. R. W. and Volkovich, Y. (2007). In-degree and PageRank: why do they follow similar power laws? Internet Math. 4, 175-198. - sourceExperimental — accuracy not yet measured
Our full-text copy of Avrachenkov, Litvak & Pham (2007) concerns the PageRank mass of the bow-tie components (IN+SCC, Pure OUT, ESCC) as a function of the damping factor c, via singular perturbation theory (Sections 3-5, pp. 3-10; Appendix A.1-A.2, pp. 12-14). No passage discusses moments of random variables X or N, or the joint existence of their moments; searches for 'moments exist', 'moment of in-degree distribution E[X]', and 'random variables X and N' returned only the component-mass and perturbation-lemma passages. The closest the paper comes is a remark (Section 4, p. 5) that 'the PageRank of pages in IN+SCC with many incoming links will increase as c increases from zero', which says nothing about moment existence. The copy is not truncated, so the claim simply is not in this paper. (LLM, conf=0.70)
plainstates an association- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Could not verify
Every source the paper cites for this claim was checked and supports it.
In the paper
“Note that the constant in (5.1) is the same as the predicted constant from [37], where we assumed that the out-degree is random and the teleportation is uniform.”
What the sources say
- Supportedcites [37] [37] Volkovich, Y., Litvak, N. and Donato, D. (2007). Determining factors behind the PageRank log-log plot. In Algorithms and Models for the Web-Graph (Lecture Notes Comput. Sci. 4863 ), Springer, Berlin, pp. 108-123. - source
Section 5 (Analytical Results) of Volkovich, Litvak & Donato (2007) states the predicted constant explicitly: C = lim k→∞ C_k = c^α(1−p0)^α / (d^α(1−c^α b)), with b = Σ p_j j^{α−1} depending on the out-degree distribution, and Section 6 uses it to predict the log-log intercepts (e.g. log10(C) giving y = −1.17x−1.73 etc.). The two qualifiers the citing sentence attributes are also in our copy: Section 3.2 says they make 'a step further allowing for random out-degrees', modelling D as i.i.d. random variables with arbitrary distribution, and Section 7 (Discussion) lists the simplifying assumptions as 'independence of certain parameters and uniform teleportation'. Whether the citing paper's own (5.1) matches that constant is the citing authors' computation, not attributed content; the identification of [37] as the source of the predicted constant under random out-degree and uniform teleportation is supported. (LLM, conf=0.90)
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: unclear — It is unclear whether the paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Supported
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Lemma 4.1. If ξ n < ∞ and βm < ∞ for some integers m,n ≥ 1 , and E (X j B k + 1 -j ) < ∞ for all 0 < j < k + 1 , where k = min (m, n) , then ρk < ∞ .”
plainstates a cause- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Rests on 4 assumptions not shown here.
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Theorem 3.2. (i) If P (B > x) = o( P (N > x)) and P (R ( 0 ) > x) = o( P (N > x)) , then, for all k ≥ 1 ,”
plainstates a cause- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Our theoretical predictions show good agreement with experimental data.”
plainstates an association- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
25 more claims
Create a free account to see all 61 claims and to verify the 8 references still open.
- Probably not a substantial claim. 17
- It may state two separate claims as one. 14
- The quote only partly states this claim. 1
Citations
Cites
Emergence of Scaling in Random Networks
Barabási, A.-L., & Albert, R. (1999) · Science · doi:10.1126/science.286.5439.509 · Cited by 36,135
The anatomy of a large-scale hypertextual Web search engine
Brin, S., & Page, L. (1998) · Computer Networks and ISDN Systems · doi:10.1016/s0169-7552(98)00110-x · Cited by 16,004
(1999) · Cited by 12,854
Authoritative sources in a hyperlinked environment
Kleinberg, J. M. (1999) · Journal of the ACM · doi:10.1145/324133.324140 · Cited by 8,959
Broder, A., Kumar, R., Maghoul, F., Raghavan, P., Rajagopalan, S., Stata, R., Tomkins, A., & Wiener, J. (2000) · Computer Networks · doi:10.1016/s1389-1286(00)00083-9 · Cited by 2,810 · cited 1×
“1 for the in-degree and PageRank, and α ≈ 2 for the out-degree [9], [32], [38].”
BackgroundA Language Modeling Approach to Information Retrieval
Ponte, J. M., & Croft, W. B. (2017) · ACM SIGIR Forum · doi:10.1145/3130348.3130368 · Cited by 2,503
A language modeling approach to information retrieval
Ponte, J. M., & Croft, W. B. (1998) · Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval · doi:10.1145/290941.291008 · Cited by 1,821
Authoritative sources in a hyperlinked environment
Kleinberg, J. M. (1998) · Symposium on Discrete Algorithms · doi:10.5555/314613.315045 · Cited by 1,814
Haveliwala, T. H. (2002) · Proceedings of the 11th international conference on World Wide Web · doi:10.1145/511446.511513 · Cited by 1,567
Google's PageRank and Beyond: The Science of Search Engine Rankings
Langville, A. N., & Meyer, C. D. (2006) · Cited by 1,204
Research works printed but not linked: 7
- Volkovich, 2008, Memorandum 1868
- Jeh, 2003, Proc. 12th Internat. Conf. World Wide Web, 271
- Kamvar, 2003, Exploiting the block structure of the Web for computing
- Kraaij, 2002, Proc. 25th Annual Internat. ACM SIGIR Conf. Research and Development in Information Retrieval, 27
- Boldi, 2005, Proc. 14th Internat. Conf. World Wide Web, 557
- Andersen, 2006, Proc. FOCS 2006, 475
- Bingham, 1989, Regular Variation
Cited by
Information ranking and power laws on trees
Jelenković, P. R., & Olvera‐Cravioto, M. (2010) · Advances in Applied Probability · doi:10.1239/aap/1293113151 · Cited by 59
Implicit Renewal Theory and Power Tails on Trees
Jelenković, P. R., & Olvera‐Cravioto, M. (2012) · Advances in Applied Probability · doi:10.1239/aap/1339878723 · Cited by 44
“Google’s PageRank algorithm [19], [27], in this section we apply the implicit renewal theory for trees developed in the previous section to the linear recursion”
MethodLocal weak convergence for PageRank
Garavaglia, A., van der Hofstad, R., & Litvak, N. (2020) · The Annals of Applied Probability · doi:10.1214/19-aap1494 · Cited by 62
“The literature [20, 43, 45, 52] usually studies the following graph-normalized equation: where (A i ) i ∈[ n ] and (B i ) i ∈[ n ] are values assigned to the vertices in the graph.”
BackgroundSelf-citationImplicit renewal theorem for trees with general weights
Jelenković, P. R., & Olvera‐Cravioto, M. (2012) · Stochastic Processes and their Applications · doi:10.1016/j.spa.2012.05.004 · Cited by 37
Asymptotics for Weighted Random Sums
Olvera‐Cravioto, M. (2012) · Advances in Applied Probability · doi:10.1239/aap/1354716592 · Cited by 39
“weights {Ci} independent of N , was introduced in [20], and has been studied in detail in [13].”
Background
Metadata
- Authors
- Volkovich, Y., & Litvak, N.
- Affiliations
- University of Twente (NL)
- Corresponding author
- Volkovich, Yana
- Litvak, Nelly
- Venue
- Advances in Applied Probability
- Publisher
- Cambridge University Press (CUP)
- Published
- 2010-06
- Volume
- 42
- Issue
- 2
- Pages
- 577-604
- ISSN
- 0001-8678 (ISSN-L)
- 1475-6064
- OpenAlex
- W2109819452
- Semantic Scholar
- 32ae967679ec6b37c7ba896b7882c14b5573f140
- 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
- bronze
- doi.org
- 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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Asymptotic analysis for personalized Web search. https://app.cochat.ai/papers/10.1239/aap/1275055243
- The paper
- Volkovich, Y., & Litvak, N. (2010). Asymptotic analysis for personalized Web search. Advances in Applied Probability. https://doi.org/10.1239/aap/1275055243
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.


