All Scale-Free Networks Are Sparse

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.

Figure 1

Graphicality transitions in scale-free networks. The plots of graphical fraction $g$ vs exponent $\gamma$ show transitions at $\gamma =0$ and $\gamma =2$. Binder’s cumulants, in the insets, identify the character of the transitions and the transition points.

Figure 2

Graphicality of the degree maximizing sequence ($N={10}^6$) given by Eq. (11) for scale-free distributions vs exponent $\gamma$. The graphicality transition points are correctly identified.