TY - JOUR

T1 - How rare are power-law networks really?

AU - Artico, I.

AU - Smolyarenko, I.

AU - Vinciotti, V.

AU - Wit, E. C.

N1 - Publisher Copyright:
© 2020 The Authors.

PY - 2020/9

Y1 - 2020/9

N2 - The putative scale-free nature of real-world networks has generated a lot of interest in the past 20 years: if networks from many different fields share a common structure, then perhaps this suggests some underlying ‘network law’. Testing the degree distribution of networks for power-law tails has been a topic of considerable discussion. Ad hoc statistical methodology has been used both to discredit power-laws as well as to support them. This paper proposes a statistical testing procedure that considers the complex issues in testing degree distributions in networks that result from observing a finite network, having dependent degree sequences and suffering from insufficient power. We focus on testing whether the tail of the empirical degrees behaves like the tail of a de Solla Price model, a two-parameter power-law distribution. We modify the well-known Kolmogorov–Smirnov test to achieve even sensitivity along the tail, considering the dependence between the empirical degrees under the null distribution, while guaranteeing sufficient power of the test. We apply the method to many empirical degree distributions. Our results show that power-law network degree distributions are not rare, classifying almost 65% of the tested networks as having a power-law tail with at least 80% power.

AB - The putative scale-free nature of real-world networks has generated a lot of interest in the past 20 years: if networks from many different fields share a common structure, then perhaps this suggests some underlying ‘network law’. Testing the degree distribution of networks for power-law tails has been a topic of considerable discussion. Ad hoc statistical methodology has been used both to discredit power-laws as well as to support them. This paper proposes a statistical testing procedure that considers the complex issues in testing degree distributions in networks that result from observing a finite network, having dependent degree sequences and suffering from insufficient power. We focus on testing whether the tail of the empirical degrees behaves like the tail of a de Solla Price model, a two-parameter power-law distribution. We modify the well-known Kolmogorov–Smirnov test to achieve even sensitivity along the tail, considering the dependence between the empirical degrees under the null distribution, while guaranteeing sufficient power of the test. We apply the method to many empirical degree distributions. Our results show that power-law network degree distributions are not rare, classifying almost 65% of the tested networks as having a power-law tail with at least 80% power.

UR - https://www.mendeley.com/catalogue/dc418cd0-e69c-388f-8a78-345b33d7e23a/

U2 - 10.1098/rspa.2019.0742

DO - 10.1098/rspa.2019.0742

M3 - Article

SN - 1364-5021

VL - 476

JO - Proceedings of the Royal Society A, Mathematical Physical and Engineering Sciences

JF - Proceedings of the Royal Society A, Mathematical Physical and Engineering Sciences

IS - 2241

M1 - 20190742

ER -