Scale-free networks are rare

Abstract

Real-world networks are often claimed to be scale free, meaning that the fraction of nodes with degree k follows a power law k − α , a pattern with broad implications for the structure and dynamics of complex systems. However, the universality of scale-free networks remains controversial. Here, we organize different definitions of scale-free networks and construct a severe test of their empirical prevalence using state-of-the-art statistical tools applied to nearly 1000 social, biological, technological, transportation, and information networks. Across these networks, we find robust evidence that strongly scale-free structure is empirically rare, while for most networks, log-normal distributions fit the data as well or better than power laws. Furthermore, social networks are at best weakly scale free, while a handful of technological and biological networks appear strongly scale free. These findings highlight the structural diversity of real-world networks and the need for new theoretical explanations of these non-scale-free patterns.

Full text

Its licence does not allow us to show the full text. Read it at PubMed Central:

References 79

1. 1.

   Albert R, Jeong H, Barabási AL. Diameter of the World-Wide Web. Nature. 1999;401:130-131.

   Not in our library10.1038/43601

2. 2.

   Pržulj N. Biological network comparison using graphlet degree distribution. Bioinformatics. 2007;23:177-183.

   Not in our library10.1093/bioinformatics/btl301

3. 3.

   Lima-Mendez G, van Helden J. The powerful law of the power law and other myths in network biology. Mol. Biosyst. 2009;5:1482-1493.

   Not in our library10.1039/b908681a

4. 4.

   Mislove, A., Marcon, M., Gummadi, K. P., Druschel, P. & Bhattacharjee, B. Measurement and analysis of online social networks. Proc. 7th ACM SIGCOMM Conference on Internet Measurement (IMC). 29–42 (San Diego, CA, USA, 2007).

   Not in our library

5. 5.
   Microbial Hub Taxa Link Host and Abiotic Factors to Plant Microbiome Variation · 2016

   No notice
6. 6.

   Ichinose G, Sayama H. Invasion of cooperation in scale-free networks: accumulated versus average payoffs. Artif. Life. 2017;23:25-33.

   Not in our library10.1162/artl_a_00220

7. 7.

   Zhang L, Small M, Judd K. Exactly scale-free scale-free networks. Phys. A. 2015;433:182-197.

   Not in our library10.1016/j.physa.2015.03.074

8. 8.

   Dorogovtsev SN, Mendes JFF. Evolution of networks. Adv. Phys. 2002;51:1079-1187.

   Not in our library10.1080/00018730110112519

9. 9.

   Barabási AL, Albert R. Emergence of scaling in random networks. Science. 1999;286:509-512.

   Not in our library10.1126/science.286.5439.509

10. 10.

    Willinger W, Alderson D, Doyle JC. Mathematics and the internet: a source of enormous confusion and great potential. Not. AMS. 2009;56:586-599.

    Not in our library

11. 11.

    Pastor-Satorras R, Vespignani A. Epidemic dynamics in finite size scale-free networks. Phys. Rev. E. 2002;65:035108.

    Not in our library10.1103/physreve.65.035108

12. 12.

    Albert R, Jeong H, Barabási AL. Error and attack tolerance of complex networks. Nature. 2000;406:378-382.

    Not in our library10.1038/35019019

13. 13.

    Carlson JM, Doyle J. Highly optimized tolerance: a mechanism for power laws in designed systems. Phys. Rev. E. 1999;60:1412-1427.

    Not in our library10.1103/physreve.60.1412

14. 14.

    Newman MEJ. Power laws, Pareto distributions and Zipf’s law. Contemp. Phys. 2005;46:323-351.

    Not in our library10.1080/00107510500052444

15. 15.

    Mitzenmacher M. A brief history of generative models for power law and lognormal distributions. Internet Math. 2003;1:226-251.

    Not in our library10.1080/15427951.2004.10129088

16. 16.

    Goh KI, Oh E, Jeong H, Kahng B, Kim D. Classification of scale-free networks. Proc. Natl Acad. Sci. USA. 2002;99:12583-12588.

    Not in our library10.1073/pnas.202301299

17. 17.

    Pastor-Satorras R, Castellano C, Van Mieghem P, Vespignani A. Epidemic processes in complex networks. Rev. Mod. Phys. 2015;87:925-979.

    Not in our library10.1103/revmodphys.87.925

18. 18.

    Pastor-Satorras R, Vespignani A. Epidemic spreading in scale-free networks. Phys. Rev. Lett. 2001;86:3200-3203.

    Not in our library10.1103/physrevlett.86.3200

19. 19.

    Aiello, W., Chung, F. R. K. & Lu, L. A random graph model for massive graphs. Proc. 32nd Annual ACM Symposium on Theory of Computing. 171–180 (Portland, OR, USA, 2000).

    Not in our library

20. 20.

    Aiello W, Chung F, Lu L. A random graph model for power law graphs. Exp. Math. 2001;10:53-66.

    Not in our library10.1080/10586458.2001.10504428

21. 21.

    Newman, M. Networks: An Introduction (Oxford Univerity Press, Oxford, 2010).

    Not in our library

22. 22.

    Newman, M. E. J. Spread of epidemic disease on networks. Phys. Rev. E66, 016128 (2002).

    Not in our library10.1103/physreve.66.016128

23. 23.

    Lee DS. Synchronization transition in scale-free networks: clusters of synchrony. Phys. Rev. E. 2005;72:1-6.

    Not in our library10.1103/physreve.72.026208

24. 24.

    Restrepo JG, Ott E, Hunt BR. Onset of synchronization in large networks of coupled oscillators. Phys. Rev. E. 2005;71:1-12.

    Not in our library10.1103/physreve.71.036151

25. 25.

    Ichinomiya T. Frequency synchronization in a random oscillator network. Phys. Rev. E. 2004;70:5.

    Not in our library10.1103/physreve.70.026116

26. 26.

    Restrepo JG, Ott E, Hunt BR. Synchronization in large directed networks of coupled phase oscillators. Chaos. 2006;16:015107.

    Not in our library10.1063/1.2148388

27. 27.

    Restrepo JG, Ott E, Hunt BR. Emergence of synchronization in complex networks of interacting dynamical systems. Phys. D. 2006;224:114-122.

    Not in our library10.1016/j.physd.2006.08.026

28. 28.

    Price DJdS. Networks of scientific papers. Science. 1965;149:510-515.

    Not in our library10.1126/science.149.3683.510

29. 29.

    Simon HA. On a class of skew distribution functions. Biometrika. 1955;42:425-440.

    Not in our library10.1093/biomet/42.3-4.425

30. 30.

    Pastor-Satorras R, Smith E, Solé RV. Evolving protein interaction networks through gene duplication. J. Theor. Biol. 2003;222:199-210.

    Not in our library10.1016/s0022-5193(03)00028-6

31. 31.

    Berger, N., Borgs, C., Chayes, J. T., D’Souza, R. M. & Kleinberg, R. D. Proc. 31st International Colloquium on Automata, Languages and Programming (ICALP). 208–221 (Turku, Finland, 2004).

    Not in our library

32. 32.

    Leskovec J, Kleinberg J, Faloutsos C. Graph evolution. ACM Trans. Knowl. Discov. Data. 2007;1:1-41.

    Not in our library10.1145/1217299.1217301

33. 33.

    Gamermann, D., Triana, J. & Jaime, R. A comprehensive statistical study of metabolic and protein-protein interaction network properties. https://arxiv.org/abs/1712.07683 (2017).

    Not in our library

34. 34.

    House, T., Read, J. M., Danon, L. & Keeling, M. J. Testing the hypothesis of preferential attachment in social network formation. EPJ Data Science, 10.1140/epjds/s13688-015-0052-2 (2015).

    Not in our library10.1140/epjds/s13688-015-0052-2

35. 35.

    A. Barabasi, Network Science (Cambridge University Press, Cambridge, UK, 2016).

    Not in our library

36. 36.

    Tanaka R. Scale-rich metabolic networks. Phys. Rev. Lett. 2005;94:1-4.

    Not in our library10.1103/physrevlett.94.168101

37. 37.

    Li L, Alderson D, Tanaka R, Doyle JC, Willinger W. Towards a theory of scale-free graphs: definition, properties, and implications (extended version). Internet Math. 2005;2:431-523.

    Not in our library10.1080/15427951.2005.10129111

38. 38.

    Stumpf MPH, Porter MA. Critical truths about power laws. Science. 2012;335:665-666.

    Not in our library10.1126/science.1216142

39. 39.

    Golosovsky M. Power-law citation distributions are not scale-free. Phys. Rev. E. 2017;032306:1-12.

    Not in our library10.1103/physreve.96.032306

40. 40.

    Stumpf MPH, Wiuf C, May RM. Subnets of scale-free networks are not scale-free: Sampling properties of networks. Proc. Natl Acad. Sci. USA. 2005;102:4221-4224.

    Not in our library10.1073/pnas.0501179102

Cited by papers we hold 5

• Networks as tools for defining emergent properties of microbiomes and their stability · 2024
  No notice
• Toward Digital Twin Oriented Modeling of Complex Networked Systems and Their Dynamics: A Comprehensive Survey · 2022
  Not checked
• Using network analysis to model the effects of the SARS Cov2 pandemic on acute patient care within a healthcare system · 2022
  Not checked
• Empirically classifying network mechanisms · 2021
  Not checked
• Activity-based epidemic propagation and contact network scaling in auto-dependent metropolitan areas · 2021
  Not checked

Reads

A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.