November 5, 2018
We bring rigor to the vibrant activity of detecting power laws in empirical degree distributions in real-world networks. We first provide a rigorous definition of power-law distributions, equivalent to the definition of regularly varying distributions that are widely used in statistics and other fields. This definition allows the distribution to deviate from a pure power law arbitrarily but without affecting the power-law tail exponent. We then identify three estimators of these exponents that are proven to be statistically consistent -- that is, converging to the true value of the exponent for any regularly varying distribution -- and that satisfy some additional niceness requirements. In contrast to estimators that are currently popular in network science, the estimators considered here are based on fundamental results in extreme value theory, and so are the proofs of their consistency. Finally, we apply these estimators to a representative collection of synthetic and real-world data. According to their estimates, real-world scale-free networks are definitely not as rare as one would conclude based on the popular but unrealistic assumption that real-world data comes from power laws of pristine purity, void of noise and deviations.
Similar papers 1
May 31, 2013
The concept of scale-free networks has been widely applied across natural and physical sciences. Many claims are made about the properties of these networks, even though the concept of scale-free is often vaguely defined. We present tools and procedures to analyse the statistical properties of networks defined by arbitrary degree distributions and other constraints. Doing so reveals the highly likely properties, and some unrecognised richness, of scale-free networks, and cast...
November 19, 2023
The power-law distribution plays a crucial role in complex networks as well as various applied sciences. Investigating whether the degree distribution of a network follows a power-law distribution is an important concern. The commonly used inferential methods for estimating the model parameters often yield biased estimates, which can lead to the rejection of the hypothesis that a model conforms to a power-law. In this paper, we discuss improved methods that utilize Bayesian i...
January 9, 2018
A central claim in modern network science is that real-world networks are typically "scale free," meaning that the fraction of nodes with degree $k$ follows a power law, decaying like $k^{-\alpha}$, often with $2 < \alpha < 3$. However, empirical evidence for this belief derives from a relatively small number of real-world networks. We test the universality of scale-free structure by applying state-of-the-art statistical tools to a large corpus of nearly 1000 network data set...
January 9, 2005
Although the ``scale-free'' literature is large and growing, it gives neither a precise definition of scale-free graphs nor rigorous proofs of many of their claimed properties. In fact, it is easily shown that the existing theory has many inherent contradictions and verifiably false claims. In this paper, we propose a new, mathematically precise, and structural definition of the extent to which a graph is scale-free, and prove a series of results that recover many of the clai...
March 31, 2020
In their recent work "Scale-free networks are rare", Broido and Clauset address the problem of the analysis of degree distributions in networks to classify them as scale-free at different strengths of "scale-freeness." Over the last two decades, a multitude of papers in network science have reported that the degree distributions in many real-world networks follow power laws. Such networks were then referred to as scale-free. However, due to a lack of a precise definition, the...
October 12, 2023
Complex networks across various fields are often considered to be scale free -- a statistical property usually solely characterized by a power-law distribution of the nodes' degree $k$. However, this characterization is incomplete. In real-world networks, the distribution of the degree-degree distance $\eta$, a simple link-based metric of network connectivity similar to $k$, appears to exhibit a stronger power-law distribution than $k$. While offering an alternative character...
February 11, 2004
This short communication uses a simple experiment to show that fitting to a power law distribution by using graphical methods based on linear fit on the log-log scale is biased and inaccurate. It shows that using maximum likelihood estimation (MLE) is far more robust. Finally, it presents a new table for performing the Kolmogorov-Smirnof test for goodness-of-fit tailored to power-law distributions in which the power-law exponent is estimated using MLE. The techniques presente...
May 21, 2021
Consensus about the universality of the power law feature in complex networks is experiencing profound challenges. To shine fresh light on this controversy, we propose a generic theoretical framework in order to examine the power law property. First, we study a class of birth-and-death networks that is ubiquitous in the real world, and calculate its degree distributions. Our results show that the tails of its degree distributions exhibits a distinct power law feature, providi...
June 10, 2015
Very often, when studying topological or dynamical properties of random scale-free networks, it is tacitly assumed that degree-degree correlations are not present. However, simple constraints, such as the absence of multiple edges and self-loops, can give rise to intrinsic correlations in these structures. In the same way that Fermionic correlations in thermodynamic systems are relevant only in the limit of low temperature, the intrinsic correlations in scale-free networks ar...
June 14, 2006
In this paper we describe the emergence of scale-free degree distributions from statistical mechanics principles. We define an energy associated to a degree sequence as the logarithm of the number of indistinguishable simple networks it is possible to draw given the degree sequence. Keeping fixed the total number of nodes and links, we show that the energy of scale-free distribution is much higher than the energy associated to the degree sequence of regular random graphs. Thi...