Scale-Free Networks and Finite Size Effects
Scale-Free Networks and Finite Size Effects
Embedded Files
A remarkable feature of many real networks is that the probability distribution of degrees (the number of links incident to each node) is highly right-skewed, with most nodes having low degree and a handful of hubs with extremely high connectivity. A special form of this kind of distributions is the power-law, which is the hallmark of scale-free networks and leads to important emergent attributes such as self-similarity in the network topology (such that any large part of the system looks like the whole), robustness to random failures and fragility to targeted attacks.
Illustration of how scale invariance in a network may be clouded by a scale imposed by the sample size.
There is much debate in the literature on whether the degree distributions of complex networks are typically power-laws or are better described by other distributions with fat tails. An important issue to consider in this debate is that real networks are not infinitely large and thus the largest degree of any network cannot be larger than the number of nodes. Finite-size scaling (FSS), firstly developed in the field of critical phenomena, is a useful tool for analyzing deviations from pure power-law behavior as due to finite size effects. In this paper we show that despite the essential differences between networks and critical phenomena, FSS provides a powerful framework for analyzing the scale-free nature of empirical networks. The basic idea is to take representations of the same network with different sizes and find two fitting parameters such that the plots of the (appropriately rescaled) degree distributions collapse on top of each other. The fidelity of the collapse plot provides a measure of self-similarity and scale-free behavior, the optimal parameters are the desired scaling exponents, and the collapsed curve is a plot of the scaling function.
We employed the FSS machinery to test the scale-free hypothesis on about two hundred large empirical networks, constructing representations at different scales in an unbiased manner. We found that such a venerable hypothesis cannot be rejected for many networks, in particular biological protein interaction networks, technological computer and hyperlink networks, and informational networks in general. Marked deviations appear in other cases, especially infrastructure and transportation but also social networks. Furthermore we showed that FSS allows discerning pure power laws from log-normal and Weibull distributions.
Scaling analysis on four real network instances: 1) The 2005 version of the proteome-scale map for human binary protein–protein interactions, 2) The word adjacency graph extracted from the English text "The Origin of Species" by C. Darwin, 3) Snapshot of the internet structure at the level of autonomous systems in 2007, 4) The collaboration graph of authors of scientific papers from database systems and logic programming (DBLP) computer science bibliography.
In conclusion, our results support the claim that scale invariance of the degree distribution is indeed a feature of many real networks, with finite size effects accounting for quantifiable deviations. We remark that our approach is inspired by statistical physics and goes beyond statistical arguments that, while powerful, overlook the true essence of the scale-free phenomena – which has meaning beyond the validity of a fit of the degree distribution.
Resources
M. Serafino, G. Cimini, A. Maritan, A. Rinaldo, S. Suweis, J. R. Banavar, G. Caldarelli. True scale-free networks hidden by finite size effects. Proceedings of the National Academy of Sciences 118(2), e2013825118 (2021)
Page updated
Google Sites
Report abuse