CoChat

In-Degree and PageRank: Why Do They Follow Similar Power Laws?

Open access
Litvak, N., Scheinhardt, W. R. W., Volkovich, Y. · 2007 · Internet Mathematics

The 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

Crossref · 10.1080/15427951.2007.10129293

Cites

27 of 27 references verified0 citation errors · 0 not checkable

Statistics

Nothing to recompute.

Figures

Figure 1 Plots for the Web data: fraction of pages with In-Degree/PageRank not less than x versus x in log-log scale, and the fitted lines.
Figure 1 Plots for the Web data: fraction of pages with In-Degree/PageRank not less than x versus x in log-log scale, and the fitted lines.From the PDF
Figure 2 The theoretical and observed differences between asymptotics of InDegree and PageRank.
Figure 2 The theoretical and observed differences between asymptotics of InDegree and PageRank.From the PDF
Figure 3 Plots for the Growing Network model: fraction of pages with InDegree/PageRank not less than x versus x in log-log scale.
Figure 3 Plots for the Growing Network model: fraction of pages with InDegree/PageRank not less than x versus x in log-log scale.From the PDF

Verification

Claims the paper makes

0 Valid · 3 Not valid · 26 Not checked · 32 Own results and interpretations

27 more claims

Create a free account to see all 61 claims and every source verdict.

See all claims — free account
  • It may state two separate claims as one. 8
  • Probably not a substantial claim. 23

Create a free account to see these claims.

Citations

Cites

Show all 27 references

Cited by

See all 62

Metadata

Authors
Litvak, N., Scheinhardt, W. R. W., & Volkovich, Y.
Venue
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
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.