In-Degree and PageRank: Why Do They Follow Similar Power Laws?
Open accessThe DOI matches its Crossref record; 27 of the 31 references it cites were found in a registry or an index; none of the 34 sources its claims cite is checked for support yet.
Abstract
PageRank is a popularity measure designed by Google to rank Web pages. Experiments confirm that PageRank values obey a power law with the same exponent as In-Degree values. This paper presents a novel mathematical model that explains this phenomenon. The relation between PageRank and In-Degree is modeled through a stochastic equation, which is inspired by the original definition of PageRank, and is analogous to the well-known distributional identity for the busy period in the _M_/_G_/1 queue. Further, we employ the theory of regular variation and Tauberian theorems to prove analytically that the tail distributions of PageRank and In-Degree differ only by a multiplicative constant, for which we derive a closed-form expression. Our analytical results are in good agreement with experimental data.
Overview
CoChat Summary
TL;DR
This paper gives a stochastic model and Tauberian analysis showing that PageRank and In-Degree have the same power-law exponent. It also derives a closed-form multiplicative constant for the asymptotic difference between their tail distributions and checks it against Web data.
Key findings
- The paper proves that the tail distributions of PageRank and In-Degree “differ only by a multiplicative constant,” while sharing the same power-law exponent.
- In the Web-data experiment on the Stanford Web graph with 281,903 nodes and ~2.3 million edges, the authors fit a slope of -1.1, corresponding to a power-law exponent α = 1.1 for both In-Degree and PageRank.
- For the same dataset, the average Out-Degree (and hence average In-Degree) was 8.2; using this value, the theoretical and observed multiplicative differences were reported as “quite close,” and for typical damping factors c between 0.8 and 0.9 the difference was 0.41, yielding a factor y(c) only 2.57 times the observed one.
- In the Growing Network simulations, the paper reports a network of 50,000 nodes with Out-Degree d = 8 and q = 0.2; the resulting plots also showed parallel log-log lines for In-Degree and PageRank, though the Web data matched the model better.
Methods
- The paper introduces a stochastic recursive equation for PageRank, based on the PageRank definition, with simplifying assumptions including constant Out-Degree and independence among certain PageRank variables.
- It models In-Degree as a regularly varying random variable via a Poisson-arrival construction on a regularly varying random interval, and then uses Laplace-Stieltjes transforms plus Tauberian theorems to analyze tail asymptotics.
- The analysis is supplemented by numerical experiments on the Stanford Web data and on a simulated Growing Network model, with power-law exponents estimated via a maximum-likelihood method.
Limitations
- The paper explicitly says the model makes “several rather severe simplifying assumptions,” especially constant Out-Degree and independence among PageRank values of pages sharing a common neighbor.
- It also states that the model “does not capture PageRank behavior to the full extent,” as shown by the discrepancy between predicted and observed multiplicative constants; this is the paper’s own stated limitation.
- Evident from the text: the theoretical model focuses on tail asymptotics and does not model some real Web-graph dependencies, such as clustering and personalization/topic sensitivity, which the authors say they would consider in further research.
Model-written summary. Check it against the paper before relying on it.
Integrity signals
Registry
Cites
Statistics
Figures



Verification
Claims the paper makes
0 Valid · 3 Not valid · 26 Not checked · 32 Own results and interpretations
None of the sources cited for this claim could be matched to a paper in Crossref, so there is nothing to check it against.
In the paper
“Our analytical results are in good agreement with experimental data.”
- Also stated in: § 1. Introduction · plain
“Our own experiments based on Web data from [Kamvar 06] are also in agreement with [Pandurangan et al. 02]”
What the sources say
- Not matchedcites Kamvar 06
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- Not matchedcites Pandurangan et al. 02
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
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.
- Also stated in: § 1. Introduction · plain
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
“Indeed, experiments show that the shape of the PageRank distribution depends on the damping factor”
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.
In the paper
“The calculations based on the maximum likelihood method (5.1) yield a slope -1 . 1”
What the sources say
- Not matchedcites [Newman 05]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
plain- 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.
- Not matched
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Clearly, these empirical values of In-Degree and PageRank lead to parallel lines for all values of the damping factor, provided that the PageRank values are reasonably large.”
boostedstates 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
“for which we derive a closed-form expression”
- Also stated in: § 1. Introduction · plain
“our analysis allows us to derive explicitly the multiplicative constant that quantifies the difference between PageRank and In-Degree tail behavior.”
plain- 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 2 assumptions not shown here.
- Also stated in: § 1. Introduction · plain
27 more claims
Create a free account to see all 61 claims and every source verdict.
- It may state two separate claims as one. 8
- Probably not a substantial claim. 23
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
An introduction to probability theory and its applications
(1958) · Journal of the Franklin Institute · doi:10.1016/0016-0032(58)90688-4 · Cited by 29,269
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
Newman (2005) · doi:10.1080/00107510500052444 · Cited by 5,749
An Introduction to Probability Theory and its Applications.
Kingman, J. F. C., & Feller, W. (1972) · Journal of the Royal Statistical Society. Series A (General) · doi:10.2307/2344620 · Cited by 4,938
Bingham, N. H., Goldie, C. M., & Teugels, J. L. (1987) · Cambridge University Press eBooks · doi:10.1017/cbo9780511721434 · Cited by 2,382
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
Langville, A., & Meyer, C. (2004) · Internet Mathematics · doi:10.1080/15427951.2004.10129091 · Cited by 894
The degree sequence of a scale‐free random graph process
Bollobás, B., Riordan, O., Spencer, J., & Tusnády, G. (2001) · Random Structures & Algorithms · doi:10.1002/rsa.1009 · Cited by 804
Problems with fitting to the power-law distribution
Goldstein, M. L., Morris, S. A., & Yen, G. G. (2004) · The European Physical Journal B · doi:10.1140/epjb/e2004-00316-5 · Cited by 495
Cited by
Fast incremental and personalized PageRank
Bahmani, B., Chowdhury, A., & Goel, A. (2010) · Proceedings of the VLDB Endowment · doi:10.14778/1929861.1929864 · Cited by 327
“…observe that not only do the global PageRank scores and in-degrees follow the same power-laws (as previously proved under mild assumptions in the literature [33]), but also the personalized PageRanks follow power-laws with average exponent roughly equal to the exponent for PageR-ank and in-degree.”
BackgroundResultInfluentialRanking and clustering of nodes in networks with smart teleportation
Lambiotte, R., & Rosvall, M. (2012) · Physical Review E · doi:10.1103/physreve.85.056107 · Cited by 108
Asymptotic analysis for personalized Web search
Volkovich, Y., & Litvak, N. (2010) · Advances in Applied Probability · doi:10.1239/aap/1275055243 · Cited by 69
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
Neighborhood randomization for link privacy in social network analysis
Fard, A. M., & Wang, K. (2013) · World Wide Web · doi:10.1007/s11280-013-0240-6 · Cited by 51
Metadata
- Authors
- Litvak, N., Scheinhardt, W. R. W., & Volkovich, Y.
- Venue
- Internet Mathematics
- Publisher
- Internet Mathematics
- Published
- 2007-01
- Volume
- 4
- Issue
- 2-3
- Pages
- 175-198
- ISSN
- 1542-7951 (ISSN-L)
- 1944-9488
- OpenAlex
- W1959086707
- Cited by
- 62
- References
- 31
- Citations by year
- 2026: 2 · 2025: 2 · 2024: 6 · 2023: 4 · 2022: 1 · 2021: 4 · 2020: 3 · 2019: 6 · 2017: 1 · 2016: 4 · 2015: 9 · 2014: 4 · 2013: 1 · 2012: 1
- FWCI
- 3.44
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- Internet Mathematics (publishedVersion)
- Project Euclid (Cornell University) (submittedVersion)
- University of Twente Research Information (submittedVersion, other-oa)
- Funders
- Nederlandse Organisatie voor Wetenschappelijk Onderzoek
- Topics
- Physical Sciences › Physics and Astronomy › Statistical and Nonlinear Physics › Complex Network Analysis Techniques
- Physical Sciences › Computer Science › Information Systems › Web visibility and informetrics
- Physical Sciences › Computer Science › Information Systems › Information Retrieval and Search Behavior
- Keywords
- PageRank, in-degree distribution, power law, tail distribution, stochastic modeling, regular variation, Tauberian theorems, web page popularity, scale-free 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.
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).
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: In-Degree and PageRank: Why Do They Follow Similar Power Laws? https://app.cochat.ai/papers/10.1080/15427951.2007.10129293
- The paper
- Litvak, N., Scheinhardt, W. R. W., & Volkovich, Y. (2007). In-Degree and PageRank: Why Do They Follow Similar Power Laws? Internet Mathematics. https://doi.org/10.1080/15427951.2007.10129293
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.