Scale-free Networks Well Done

Ivan Voitalov, Pim van der Hoorn, Remco van der Hofstad, Dmitri Krioukov
arXiv
1811.02071
November 5, 2018

Abstract

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 in statistics. 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 exponent value for any regularly varying distribution -- and that satisfy some additional niceness requirements. 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.