pith. sign in

arxiv: 2606.19583 · v1 · pith:WUQVZOQPnew · submitted 2026-06-17 · 🧮 math.PR

Power-law hypothesis and (un)fairness of PageRank on undirected multi-type PAMs

Christian Borgs , Florian Henning , Remco van der Hofstad , Nelly Litvak This is my paper

Pith reviewed 2026-06-26 19:26 UTC · model grok-4.3

classification 🧮 math.PR
keywords preferential attachment modelPageRankpower-law distributionmulti-type networksundirected graphscolor-dependent exponentsfairness
0
0 comments X

The pith

In undirected multi-type preferential attachment models with finite colors, PageRank follows a power law whose exponent depends on vertex color for some initial distributions and attractiveness functions.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that the power-law hypothesis for PageRank holds in the undirected multi-type PAM, extending single-type undirected results and complementing directed multi-type analyses. Unlike the directed case, the exponent here can vary by color depending on the initial color distribution and attractiveness function. This matters for fairness because, in the two-color case, it implies that PageRank-based sampling may systematically under- or over-represent nodes of certain colors. The central mechanism is the sequential growth rule of the colored undirected PAM, analyzed asymptotically for finite colors.

Core claim

For the case of a finite set of colors, the power-law hypothesis for PageRank is fulfilled also for the colored undirected PAM, where, by contrast to the directed case, the power-law exponent is color-dependent for some choices of the initial color distribution and the attractiveness function. For the specific case of a two-type model, implications of the results on fairness in sampling underrepresented nodes from the network are discussed.

What carries the argument

The multi-type undirected preferential attachment model, in which vertices receive one of finitely many colors and new edges attach according to an attractiveness function that can depend on color and degree.

If this is right

  • PageRank obeys power-law tails in the colored undirected PAM.
  • The tail exponent can differ by color under certain initial conditions and attractiveness rules.
  • In the two-color case this produces measurable differences in the probability that a low-color node ranks high under PageRank sampling.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Color-dependent exponents could create persistent sampling bias when PageRank is used to select nodes in growing networks that evolve under undirected preferential attachment.
  • The fairness gap identified for two colors suggests checking whether real citation or collaboration networks exhibit similar color-dependent ranking tails when vertices are labeled by institution type or topic.
  • Extending the finite-color analysis to a continuum of colors might reveal whether the dependence survives in the limit or averages out.

Load-bearing premise

The model uses a finite number of colors together with an attractiveness function and initial color distribution that permit the PageRank exponent to become color-dependent.

What would settle it

A direct simulation of the two-type undirected PAM with the specific attractiveness and initial distribution parameters would show identical PageRank exponents across colors.

read the original abstract

The preferential attachment model (PAM) describes the sequential growth of a network based on the "rich-get-richer" principle. Several versions of it have become established for modeling, e.g., citation networks, capturing a power-law degree distribution. Directed versions of the preferential attachment model where the edges are directed from the new to the old vertices have been the subject of extensive research. They have been shown to exhibit remarkable properties such as heavier tails for the limiting graph-normalized PageRank than for the in-degrees. By contrast, for the undirected version, we recently showed that PageRank has similar tails as the degree. In the present paper, we discuss the PageRank asymptotics for a multi-type version of the undirected PAM (here vertices have different colors), complementing previous results of Antunes, Bhamidi, Banerjee and Pipiras on the asymptotics of PageRank on similar directed multi-type or colored PAMs. Our studies are motivated by the aim to go beyond the rigid rule of edge orientation in directed preferential attachment models. As the main result, for the case of a finite set of colors, we show that the power-law hypothesis for PageRank is fulfilled also for the colored undirected PAM, where, by contrast to the directed case, the power-law exponent is color-dependent for some choices of the initial color distribution and the attractiveness function. For the specific case of a two-type model, we discuss implications of our results on fairness in sampling underrepresented nodes from the network.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper studies PageRank asymptotics in undirected multi-type preferential attachment models (PAMs) with a finite number of vertex colors. The central claim is that the power-law hypothesis holds for the limiting graph-normalized PageRank scores. Unlike the directed multi-type case, the power-law exponent is shown to be color-dependent for some choices of the initial color distribution and attractiveness function. The result is obtained by extending asymptotic analysis from the single-type undirected PAM and from prior directed multi-type results. For the two-type model the authors discuss implications for fairness when sampling underrepresented nodes.

Significance. If the derivations hold, the work supplies a rigorous extension of PageRank tail results to the undirected colored setting and isolates a mechanism (initial distribution plus attractiveness) that produces color-dependent exponents. This clarifies how edge orientation affects heterogeneity in centrality measures and supplies a mathematical basis for fairness considerations in network sampling. The paper builds directly on the authors' prior undirected single-type analysis and on Antunes-Bhamidi-Banerjee-Pipiras directed multi-type results.

minor comments (2)
  1. [Abstract] The abstract states that the power-law hypothesis is fulfilled but does not record the precise form of the limiting tail or the admissible range of the color-dependent exponent; adding one sentence with the exponent expression would improve readability.
  2. [Section 2] Section 2 (model definition) introduces the multi-type undirected PAM via a specific attractiveness function and initial color distribution; a short remark clarifying which of these choices are essential for color-dependence versus which are merely illustrative would help readers distinguish the general theorem from the two-type discussion.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. No specific major comments appear in the report, so we have no points requiring direct response or manuscript changes at this stage.

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper frames its main result as a mathematical proof of the power-law hypothesis for PageRank in the finite-color undirected multi-type PAM, derived from the model construction and asymptotic analysis techniques. It extends prior single-type undirected results (mentioned as 'we recently showed') but does not reduce the new color-dependent exponent claim to a fitted parameter, self-definition, or unverified self-citation chain. The derivation is presented as self-contained against the stated model assumptions and external benchmarks from directed cases, with no quoted steps that collapse by construction to inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the standard probabilistic construction of the multi-type preferential attachment model, limit theorems for degree and PageRank distributions, and the assumption that the attractiveness function and initial color distribution permit color-dependent exponents.

axioms (2)
  • standard math Standard axioms of probability theory and measure theory for defining random graph sequences and their asymptotic limits.
    The paper is in math.PR and relies on convergence results for graph-valued processes.
  • domain assumption The multi-type undirected PAM is defined via the given attractiveness function and color distribution rules from prior literature.
    The result is stated for this specific model family.

pith-pipeline@v0.9.1-grok · 5812 in / 1386 out tokens · 34976 ms · 2026-06-26T19:26:04.257749+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

21 extracted references · 14 canonical work pages

  1. [1]

    Michael Steele

    D. Aldous and J. Steele, “The objective method: Probabilistic combinatorial optimiza- tion and local weak convergence,” inProbability on discrete structures, ser. Encyclopae- dia Math. Sci. Vol. 110, Springer, 2004, pp. 1–72.doi:10.1007/978-3-662-09444-0_1

    work page doi:10.1007/978-3-662-09444-0_1 2004

  2. [2]

    Asymptotic fringe distributions for general families of random trees,

    D. Aldous, “Asymptotic fringe distributions for general families of random trees,”Ann. Appl. Probab., vol. 1, no. 2, pp. 228–266, 1991,issn: 1050-5164,2168-8737.doi:10 . 1214/aoap/1177005936

    arXiv 1991

  3. [3]

    Attribute network models, stochastic approximation and network sampling,

    N. Antunes, S. Banerjee, S. Bhamidi, and V. Pipiras, “Attribute network models, stochastic approximation and network sampling,”Ann. Appl. Probab., vol. 36, no. 1, pp. 652–702, 2026,issn: 1050-5164,2168-8737.doi:10.1214/25-AAP2243 24

    work page doi:10.1214/25-aap2243 2026

  4. [4]

    Homophily and the glass ceiling effect in social networks,

    C. Avin, B. Keller, Z. Lotker, C. Mathieu, D. Peleg, and Y.-A. Pignolet, “Homophily and the glass ceiling effect in social networks,” inITCS’15—Proceedings of the 6th Innovations in Theoretical Computer Science, ACM, New York, 2015, pp. 41–50,isbn: 978-1-4503-3333-7. [Online]. Available:https://www.irif.fr/_media/users/claire/ glassceilingpaper.pdf

    2015

  5. [5]

    PageRank asymptotics on directed preferential attachment networks,

    S. Banerjee and M. Olvera-Cravioto, “PageRank asymptotics on directed preferential attachment networks,”Ann. Appl. Probab., vol. 32, no. 4, pp. 3060–3084, 2022,issn: 1050-5164,2168-8737.doi:10.1214/21-aap1757

    work page doi:10.1214/21-aap1757 2022

  6. [6]

    Bellman, R

    A.-L. Barab´ asi and R. Albert, “Emergence of scaling in random networks,”Science, vol. 286, no. 5439, pp. 509–512, 1999.doi:10.1126/science.286.5439.509

    work page doi:10.1126/science.286.5439.509 1999

  7. [7]

    Recurrence of distributional limits of finite planar graphs,

    I. Benjamini and O. Schramm, “Recurrence of distributional limits of finite planar graphs,”Electron. J. Probab., vol. 6, no. 23, 13, 2001,issn: 1083-6489.doi:10.1214/ EJP.v6-96

    2001

  8. [8]

    Asymptotic behavior and distribu- tional limits of preferential attachment graphs,

    N. Berger, C. Borgs, J. T. Chayes, and A. Saberi, “Asymptotic behavior and distribu- tional limits of preferential attachment graphs,”Ann. Probab., vol. 42, no. 1, pp. 1–40, 2014.doi:10.1214/12-AOP755

    work page doi:10.1214/12-aop755 2014

  9. [9]

    First to market is not everything: An analysis of preferential attachment with fitness,

    C. Borgs, J. Chayes, C. Daskalakis, and S. Roch, “First to market is not everything: An analysis of preferential attachment with fitness,” inProceedings of the Thirty-Ninth An- nual ACM Symposium on Theory of Computing, ser. STOC ’07, San Diego, California, USA: Association for Computing Machinery, 2007, pp. 135–144,isbn: 9781595936318. doi:10.1145/125079...

    work page doi:10.1145/1250790.1250812 2007

  10. [10]

    A preferential attachment model with random initial degrees,

    M. Deijfen, H. van den Esker, R. van der Hofstad, and G. Hooghiemstra, “A preferential attachment model with random initial degrees,”Ark. Mat., vol. 47, no. 1, pp. 41–72, 2009,issn: 0004-2080,1871-2487.doi:10.1007/s11512-007-0067-4

    work page doi:10.1007/s11512-007-0067-4 2009

  11. [11]

    A geometric preferential attachment model of networks,

    A. D. Flaxman, A. M. Frieze, and J. Vera, “A geometric preferential attachment model of networks,”Internet Math., vol. 3, no. 2, pp. 187–205, 2006. [Online]. Available:http: //projecteuclid.org/euclid.im/1204906138

    arXiv 2006

  12. [12]

    Universality of the local limit of preferential attachment models,

    A. Garavaglia, R. Hazra, R. van der Hofstad, and R. Ray, “Universality of the local limit of preferential attachment models,”To appear in Ann. Appl. Probab., 2022. arXiv: 2212.05551

    arXiv 2022

  13. [13]

    Local weak convergence for PageR- ank,

    A. Garavaglia, R. van der Hofstad, and N. Litvak, “Local weak convergence for PageR- ank,”Ann. Appl. Probab., vol. 30, no. 1, pp. 40–79, 2020.doi:10.1214/19-AAP1494

    work page doi:10.1214/19-aap1494 2020

  14. [14]

    Power-law hypothesis for PageRank on undirected graphs,

    F. Henning, R. van der Hofstad, and N. Litvak, “Power-law hypothesis for PageRank on undirected graphs,”Electron. J. Probab., vol. 30, Paper No. 153, 27, 2025,issn: 1083-6489.doi:10.1214/25-ejp1415

    work page doi:10.1214/25-ejp1415 2025

  15. [15]

    van der Hofstad,Random graphs and complex networks

    R. van der Hofstad,Random graphs and complex networks. Vol. 1(Cambridge Series in Statistical and Probabilistic Mathematics). Cambridge University Press, Cambridge, 2017, vol. [43], pp. xvi+321,isbn: 978-1-107-17287-6.doi:10.1017/9781316779422

    work page doi:10.1017/9781316779422 2017

  16. [16]

    van der Hofstad,Random Graphs and Complex Networks

    R. van der Hofstad,Random Graphs and Complex Networks. Vol. 2(Cambridge Series in Statistical and Probabilistic Mathematics). Cambridge University Press, 2024,isbn: 9781316795552.doi:10.1017/9781316795552

    work page doi:10.1017/9781316795552 2024

  17. [17]

    Are giants in random digraphs ‘almost’ local?

    R. van der Hofstad and M. Pandey, “Are giants in random digraphs ‘almost’ local?” Electron. Commun. Probab., vol. 30, 2025,issn: 1083-589X.doi:10.1214/25-ecp694

    work page doi:10.1214/25-ecp694 2025

  18. [18]

    Geometric preferential attachment in non-uniform metric spaces,

    J. Jordan, “Geometric preferential attachment in non-uniform metric spaces,”Electron. J. Probab., vol. 18, no. 8, 15, 2013,issn: 1083-6489.doi:10.1214/EJP.v18-2271 25

    work page doi:10.1214/ejp.v18-2271 2013

  19. [19]

    Karimi, M

    F. Karimi, M. G´ enois, C. Wagner, P. Singer, and M. Strohmaier, “Homophily influences ranking of minorities in social networks,”Scientific Reports, vol. 11077, no. 8, 2018.doi: 10.1038/s41598-018-29405-7

    work page doi:10.1038/s41598-018-29405-7 2018

  20. [20]

    Fairness rising from the ranks: Hits and pagerank on homophilic networks,

    A. A. Stoica, N. Litvak, and A. Chaintreau, “Fairness rising from the ranks: Hits and pagerank on homophilic networks,” English, inWWW ’24, 33rd ACM Web Confer- ence, WWW 2024 ; Conference date: 13-05-2024 Through 17-05-2024, United States: Association for Computing Machinery, Inc., May 2024, pp. 2594–2602.doi:10.1145/ 3589334.3645609

    arXiv 2024

  21. [21]

    Williams,Probability with Martingales

    D. Williams,Probability with Martingales. Cambridge University Press, 1991.doi:10. 1017/CBO9780511813658 26

    1991