Inhomogeneous random graphs: how heavy tails reshape connectivity
Abstract
We study inhomogeneous random graphs on n vertices with independent Pareto weights of parameter α>0 and connection probabilities min(εn WiWj, 1). Our main focus is the infinite-mean regime 0<α<1. Under the scaling nεnα=λ, with λ>0 fixed, the global architecture of the graph is entirely governed by the Poisson point process Π of rescaled extreme weights. In particular, the size of the largest component, divided by n, converges to a non-degenerate random variable expressed as an explicit functional of Π. Through the point process Π, we also characterize the exact limiting connectivity probability, uncovering a non-sharp connectivity threshold. The second largest component and the diameter of the largest component are bounded with high probability. The distance between two uniformly chosen vertices in the largest component is at most three with high probability. We also prove convergence of the point process of rescaled degrees and identify the limiting distribution of the maximum degree. For completeness, we obtain expected degree asymptotics, typical degree limits and connectivity regimes for all α>0. Due to the failure of classical branching process approximations in the infinite-mean regime, our approach relies fundamentally on analyzing the extreme weight environment Π.
Related
- Spectrum of Directed Inhomogeneous Random Graphs
- Higher-Order Fluctuations of the Log-Partition Function for Ising Models on Inhomogeneous Random Graphs
- Two-Sample Testing for Inhomogeneous Random Graphs in Non-Integral Lr Norms
- Perron-Wright asymptotics and critical component processes for regular inhomogeneous random graphs
- Maximum degree for random geometric graphs in the connectivity regime and beyond
BibTeX
@misc{andreis2026inhomogeneous,
title = {{Inhomogeneous random graphs: how heavy tails reshape connectivity}},
author = {Luisa Andreis and Luca Avena and Rajat Subhra Hazra and Elena Matteini},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.29564},
eprint = {2610.29564},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.29564},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Inhomogeneous random graphs: how heavy tails reshape connectivity
AU - Luisa Andreis
AU - Luca Avena
AU - Rajat Subhra Hazra
AU - Elena Matteini
PY - 2026
DA - 2026/10/21
PB - arXiv
DO - 10.48550/arxiv.2610.29564
UR - https://arxiv.org/abs/2610.29564
AB - We study inhomogeneous random graphs on n vertices with independent Pareto weights of parameter α>0 and connection probabilities min(ε_n W_iW_j, 1). Our main focus is the infinite-mean regime 0<α<1. Under the scaling nε_n^α=λ, with λ>0 fixed, the global architecture of the graph is entirely governed by the Poisson point process Π of rescaled extreme weights. In particular, the size of the largest component, divided by n, converges to a non-degenerate random variable expressed as an explicit functional of Π. Through the point process Π, we also characterize the exact limiting connectivity probability, uncovering a non-sharp connectivity threshold. The second largest component and the diameter of the largest component are bounded with high probability. The distance between two uniformly chosen vertices in the largest component is at most three with high probability. We also prove convergence of the point process of rescaled degrees and identify the limiting distribution of the maximum degree. For completeness, we obtain expected degree asymptotics, typical degree limits and connectivity regimes for all α>0. Due to the failure of classical branching process approximations in the infinite-mean regime, our approach relies fundamentally on analyzing the extreme weight environment Π.
ER -