Scale-free Networks Well Done*

We bring rigor to the vibrant activity of detecting power laws in empirical degree distributions in real networks. We first provide rigorous definitions of scale-free and power-law distributions, the latter equivalent to the definition of regularly varying distributions in statistics. These definitions allow 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 data to find that real scale-free networks are definitely not as rare as one would conclude based on the popular but unrealistic assumption that real data comes from power laws of pristine purity, void of noise and deviations.