Source-linked AI summary
All scale-free networks are sparse
Charo I. Del Genio, Thilo Gross, Kevin E. Bassler
TL;DR
The paper asks why dense scale-free networks are absent and studies when power-law degree sequences can be realized as simple graphs. Using analytical reasoning, numerical tests, and an extreme-value-based construction, it finds discontinuous realizability transitions at γ = 0 and γ = 2, explaining why large unconstrained scale-free networks are sparse.
Problem
The paper investigates why dense scale-free networks are not observed, despite power-law networks with γ < 2 having diverging mean degree in the thermodynamic limit.
Method
The authors combine the Erdős-Gallai graphicality criterion, numerical ensembles of degree sequences, analytical reasoning, and degree-maximizing sequences built using extreme-value arguments.
Results
Graphicality undergoes two discontinuous, first-order transitions at γ = 0 and γ = 2; in the large-system limit, unbounded power-law sequences with 0 < γ < 2 are not realizable.
Takeaways & Limitations
Large scale-free networks are sparse because they either have γ > 2 or require a degree cutoff; dense power-law networks with γ < 0 lack commonly associated scale-free properties.
Abstract
from arXiv · showhide
We study the realizability of scale free-networks with a given degree sequence, showing that the fraction of realizable sequences undergoes two first-order transitions at the values 0 and 2 of the power-law exponent. We substantiate this finding by analytical reasoning and by a numerical method, proposed here, based on extreme value arguments, which can be applied to any given degree distribution. Our results reveal a fundamental reason why large scale-free networks without constraints on minimum and maximum degree must be sparse.