Scale-free networks are rare

Abstract

Real-world networks are often claimed to be scale free, meaning that the fraction of nodes with degree k follows a power law k^-α, a pattern with broad implications for the structure and dynamics of complex systems. However, the universality of scale-free networks remains controversial. Here, we organize different definitions of scale-free networks and construct a severe test of their empirical prevalence using state-of-the-art statistical tools applied to nearly 1000 social, biological, technological, transportation, and information networks. Across these networks, we find robust evidence that strongly scale-free structure is empirically rare, while for most networks, log-normal distributions fit the data as well or better than power laws. Furthermore, social networks are at best weakly scale free, while a handful of technological and biological networks appear strongly scale free. These findings highlight the structural diversity of real-world networks and the need for new theoretical explanations of these non-scale-free patterns.

Fig. 1

Mean degree $⟨k⟩$ as a function of the number of nodes n. The 928 network data sets in the corpus studied here vary broadly size and density. For data sets with more than one degree sequence (see text), we plot the median of the corresponding set of mean degrees

Fig. 2

Taxonomy of scale-free network definitions. Super-Weak meaning that a power law is not necessarily a statistically plausible model of a network’s degree distribution but it is less implausible than alternatives; Weakest, meaning a degree distribution that is plausibly power-law distributed; Weak, adds a requirement that the distribution’s scale-free portion cover at least 50 nodes; Strong, adds a requirement that $2<\widehat{\alpha }<3$ and the Super-Weak constraints; and, Strongest, meaning that almost every associated simple graph can meet the Strong constraints. The Super-Weak overlaps with the Weak definitions and contains the Strong definitions as special cases. Networks that fail to meet any of these criteria are deemed Not Scale Free

Fig. 3

Distribution of $\widehat{\alpha }$ by scale-free evidence category. For networks with more than one degree sequence, the median estimate is used, and for visual clarity the 8% of networks with a median $\widehat{\alpha }\ge 7$ are omitted

Fig. 4

Proportion of networks by scale-free evidence category. Bars separate the Super-Weak category from the nested definitions, and from the Not Scale Free category, defined as networks that are neither Weakest or Super-Weak

Fig. 5

Proportion of networks by scale-free evidence category and by domain. a Biological networks, b social networks, and c technological networks. Tickers show change in percent from the pattern in all of the data sets

Fig. 6

Proportions of networks in each scale-free evidence category with removed degree percentage requirements

Fig. 7

Moment ratio scaling. For 3662 degree sequences, the empirical ratio of the second to first moments $⟨k^2⟩∕⟨{k⟩}^2$ as a function of network size n, showing substantial variation across networks and domains, little evidence of the divergence pattern expected for scale-free distributions, and perhaps a roughly sublinear scaling relationship (smoothed mean via exponential kernel, with smoothed standard deviations)