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
Scaling personalized web search
Jeh, G., & Widom, J. (2003) · Proceedings of the twelfth international conference on World Wide Web - WWW '03 · doi:10.1145/775152.775191 · Cited by 1,195 · cited 1×
“Modular PageRank, which was proposed by Jeh and Widom in [18], is similar to the above approach.”
ResultLeskovec, J., & Faloutsos, C. (2006) · Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1150402.1150479 · Cited by 1,170
Combating Web Spam with TrustRank
Gyöngyi, Z., Garcia-Molina, H., & Pedersen, J. (2004) · Proceedings 2004 VLDB Conference · doi:10.1016/b978-012088469-8.50052-8 · Cited by 1,085
Topic-sensitive pagerank: A context-sensitive ranking algorithm for web search
Haveliwala, T. H. (2003) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2003.1208999 · Cited by 1,052
Local Graph Partitioning using PageRank Vectors
Andersen, R., Chung, F., & Lang, K. (2006) · 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06) · doi:10.1109/focs.2006.44 · Cited by 967 · cited 1×
“Hence, PageRank is successfully used for spam detection [15], graph partitioning [1], and finding gems in scientific citations [10], to name just a few.”
MethodGoogle's PageRank and Beyond: The Science of Search Engine Rankings
Langville, A. N., & Meyer, C. D. (2006) · doi:10.1515/9781400830329 · Cited by 814
Finding scientific gems with Google’s PageRank algorithm
Chen, P., Xie, H., Maslov, S., & Redner, S. (2007) · Journal of Informetrics · doi:10.1016/j.joi.2006.06.001 · Cited by 483
Research and Development in Information Retrieval
(1983) · Lecture Notes in Computer Science · doi:10.1007/bfb0036332 · Cited by 378
The Intelligent surfer: Probabilistic Combination of Link and Content Information in PageRank
Richardson, M., & Domingos, P. (2001) · Cited by 356
The Importance of Prior Probabilities for Entry Page Search
Kraaij, W., Westerveld, T., & Hiemstra, D. (2002) · Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval · doi:10.1145/564376.564383 · Cited by 268
Jessen, H., & Mikosch, T. (2006) · Publications de l'Institut Mathematique · doi:10.2298/pim0694171j · Cited by 236 · cited 1×
“[6], and to the recent review by Jessen and Mikosch [20].”
ResultAn Analytical Comparison of Approaches to Personalizing PageRank
Haveliwala, T. H., Kamvar, S. D., & Jeh, G. (2003) · Cited by 208
Personalized Search on the World Wide Web
Micarelli, A., Gasparetti, F., Sciarrone, F., & Gauch, S. (2007) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-72079-9_6 · Cited by 195
PageRank as a function of the damping factor
Boldi, P., Santini, M., & Vigna, S. (2005) · Proceedings of the 14th international conference on World Wide Web - WWW '05 · doi:10.1145/1060745.1060827 · Cited by 195
Using PageRank to Characterize Web Structure
Pandurangan, G., Raghavan, P., & Upfal, E. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-45655-4_36 · Cited by 164
Fixed points of a generalized smoothing transformation and applications to the branching random walk
Liu, Q. (1998) · Advances in Applied Probability · doi:10.1239/aap/1035227993 · Cited by 150
Approximating PageRank from In-Degree
Fortunato, S., Boguñá, M., Flammini, A., & Menczer, F. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-78808-9_6 · Cited by 134
Asymptotic properties and absolute continuity of laws stable by random weighted mean
Liu, Q. (2001) · Stochastic Processes and their Applications · doi:10.1016/s0304-4149(01)00092-8 · Cited by 108
On the asymptotic behaviour of the distributions of the busy period and service time in M/G/ 1
Meyer, A. D., & Teugels, J. L. (1980) · Journal of Applied Probability · doi:10.2307/3212973 · Cited by 94
Using PageRank to Characterize Web Structure
Pandurangan, G., Raghavan, P., & Upfal, E. (2006) · Internet Mathematics · doi:10.1080/15427951.2006.10129114 · Cited by 86
Local Partitioning for Directed Graphs Using PageRank
Andersen, R., Chung, F., & Lang, K. (2008) · Internet Mathematics · doi:10.1080/15427951.2008.10129297 · Cited by 72
Queueing systems with heavy tails
Zwart, A. B. (2001) · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · doi:10.6100/ir547196 · Cited by 63
In-Degree and PageRank: Why Do They Follow Similar Power Laws?
Litvak, N., Scheinhardt, W. R. W., & Volkovich, Y. (2007) · Internet Mathematics · doi:10.1080/15427951.2007.10129293 · Cited by 62
Self-citationInformation 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
Local Partitioning for Directed Graphs Using PageRank
Andersen, R., Chung, F., & Lang, K. (2007) · Springer eBooks · doi:10.1007/978-3-540-77004-6_13 · Cited by 58
Information ranking and power laws on trees
Jelenković, P. R., & Olvera‐Cravioto, M. (2010) · Advances in Applied Probability · doi:10.1017/s0001867800004523 · Cited by 53
RANDOM WALKS ON DIRECTED NETWORKS: THE CASE OF PAGERANK
FORTUNATO, S., & FLAMMINI, A. (2007) · International Journal of Bifurcation and Chaos · doi:10.1142/s0218127407018439 · Cited by 46
PageRank of Scale-Free Growing Networks
Avrachenkov, K., & Lebedev, D. (2006) · Internet Mathematics · doi:10.1080/15427951.2006.10129120 · Cited by 44
Determining Factors Behind the PageRank Log-Log Plot
Volkovich, Y., Litvak, N., & Donato, D. (2007) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-77004-6_9 · Cited by 31 · cited 4×
“We persuade the idea suggested at [18, 27] for the case of the personalized PageRank.”
BackgroundInfluentialSelf-citationDistribution of PageRank Mass Among Principle Components of the Web
Avrachenkov, K., Litvak, N., & Pham, K. S. (2007) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-77004-6_2 · Cited by 29 · cited 1×
“Denoting the total number of nodes in the Web graph by w , we get that the probability to follow a particular link from such page becomes 1 /w, and it is almost zero for large w .”
BackgroundSelf-citationRoss, S. M. (2003) · Probability in the Engineering and Informational Sciences · doi:10.1017/s0269964803171033 · Cited by 23
Using Polynomial Chaos to Compute the Influence of Multiple Random Surfers in the PageRank Model
Constantine, P. G., & Gleich, D. F. (2007) · Springer eBooks · doi:10.1007/978-3-540-77004-6_7 · Cited by 21
Algorithms and Models for the Web-Graph
(2007) · Lecture notes in computer science · doi:10.1007/978-3-540-77004-6 · Cited by 17
Extremal Dependencies and Rank Correlations in Power Law Networks
Volkovich, Y., Litvak, N., & Zwart, B. (2009) · Lecture notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering · doi:10.1007/978-3-642-02469-6_43 · Cited by 14
Self-citationOn the asymptotic behaviour of the distributions of the busy period and service time in M/G/1
Meyer, A. D., & Teugels, J. L. (1980) · Journal of Applied Probability · doi:10.1017/s0021900200033908 · Cited by 13
Characterization of Tail Dependence for In-Degree and PageRank
Litvak, N., Scheinhardt, W., Volkovich, Y., & Zwart, B. (2009) · Lecture notes in computer science · doi:10.1007/978-3-540-95995-3_8 · Cited by 6
Self-citationIn-Degree and PageRank of Web pages: Why do they follow similar power laws?Preprint
Litvak, N., Scheinhardt, W., & Volkovich, Y. (2006) · arXiv (Cornell University) · doi:10.48550/arxiv.math/0607507 · Cited by 5
Self-citationA framework for evaluating statistical dependencies and rank correlations in power law graphs
Volkovich, Y., Litvak, N., & Zwart, B. (2008) · Data Archiving and Networked Services (DANS) · Cited by 4
Self-citationInformation Ranking and Power Laws on TreesPreprint
Jelenković, P. R., & Olvera‐Cravioto, M. (2009) · arXiv (Cornell University) · doi:10.48550/arxiv.0905.1738
Resnick, S. I. (2007) · Springer Series in Operations Research and Financial Engineering · doi:10.1007/978-0-387-45024-7
Ross, S. M. (2004) · Encyclopedia of Statistical Sciences · doi:10.1002/0471667196.ess1246
Research works printed but not linked: 3
- [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. -
- [6] Bingham, N. H., Goldie, C. M. and Teugels, J. L. (1989). Regular Variation . Cambridge University Press. -
- 10.1017/s0001867800008090 · doi:10.1017/s0001867800008090
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
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.


