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

41. 41.

    Jackson MO, Rogers BW. Meeting strangers and friends of friends: how random are social networks? Am. Econ. Rev. 2007;97:890-915.

    Not in our library10.1257/aer.97.3.890

42. 42.

    Khanin, R. & Wit, E. How scale-free are biological networks. J. Comp. Biol. 13, 810-818 (2006).

    Not in our library10.1089/cmb.2006.13.810

43. 43.

    Adamic LA, Huberman BA. Technical comment on power-law distribution of the world wide web by A.-L. Barabási and R. Albert and H. Jeong and G. Bianconi. Science. 2000;287:2115.

    Not in our library10.1126/science.287.5461.2115a

44. 44.

    Dorogovtsev, S. N., Mendes, J. F. F. & Samukhin, A. N. Generic scale of the “scale-free” growing networks. https://arxiv.org/abs/cond-mat/0011115 (2000).

    Not in our library

45. 45.

    Redner S. How popular is your paper? An empirical study of the citation distribution. Eur. Phys. J. B. 1998;134:131-134.

    Not in our library10.1007/s100510050359

46. 46.

    Pachon A, Sacerdote L, Yang S. Scale-free behavior of networks with the copresence of preferential and uniform attachment rules. Phys. D: Nonlinear Phenom. 2018;371:1-12.

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

47. 47.

    Seshadhri C, Pinar A, Kolda TG. An in-depth analysis of stochastic Kronecker graphs. J. ACM. 2011;60:1-30.

    Not in our library10.1145/2450142.2450149

48. 48.

    Eikmeier, N. & Gleich, D. F. Proc. 23rd ACM SIGKDD Internat. Conference on Knowledge Discovery and Data Mining (KDD). 817–826 (Halifax, NS, Canada, 2017).

    Not in our library

49. 49.

    Clauset A, Shalizi CR, Newman MEJ. Power-law distributions in empirical data. SIAM Rev. 2009;51:661-703.

    Not in our library10.1137/070710111

50. 50.

    Song C, Havlin S, Makse H. Self-similarity of complex networks. Nature. 2005;433:392-395.

    Not in our library10.1038/nature03248

51. 51.

    Dmitri Krioukov MAacuteS, Boguñá M. Self-similarity of complex networks and hidden metric spaces. Phys. Rev. Lett. 2008;100:078701.

    Not in our library10.1103/physrevlett.100.078701

52. 52.

    Alderson DL, Li L. Diversity of graphs with highly variable connectivity. Phys. Rev. E. 2007;75:046102.

    Not in our library10.1103/physreve.75.046102

53. 53.

    Mitzenmacher M. Editorial: the future of power law research. Internet Math. 2004;2:525-534.

    Not in our library10.1080/15427951.2005.10129112

54. 54.

    Middendorf M, Ziv E, Wiggins CH. Inferring network mechanisms: The Drosophila melanogaster protein interaction network. Proc. Natl Acad. Sci. USA. 2005;102:3192-3197.

    Not in our library10.1073/pnas.0409515102

55. 55.

    Newman MEJ. The first-mover advantage in scientific publication. EPL. 2009;86:68001.

    Not in our library10.1209/0295-5075/86/68001

56. 56.

    Redner S. Citation statistics from 110 years of physical review. Phys. Today. 2005;58:49-54.

    Not in our library10.1063/1.1996475

57. 57.

    Radicchi, F., Fortunato, S. & Castellano, C. Universality of citation distributions: toward an objective measure of scientific impact. Proc. Natl Acad. Sci. USA105, 17268–17272 (2008).

    Not in our library10.1073/pnas.0806977105

58. 58.

    Mayo, D. G. Error and the Growth of Experimental Knowledge (Science and Its Conceptual Foundations series) (University of Chicago Press, Chicago, IL,1996).

    Not in our library

59. 59.

    Clauset, A., Tucker, E. & Sainz, M. The Colorado Index of Complex Networks, sanitize@url url icon.colorado.edu (2016).

    Not in our library

60. 60.

    Vuong QH. Likelihood ratio tests for model selection and non-nested hypotheses. Econometrica. 1989;57:307-333.

    Not in our library10.2307/1912557

61. 61.

    Claeskens G, Hjort NL. Model Selection and Model Averaging. 2008.

    Not in our library

62. 62.

    Lee SH, Fricker MD, Porter MA. Mesoscale analyses of fungal networks as an approach for quantifying phenotypic traits. J. Complex Netw. 2017;5:145-159.

    Not in our library

63. 63.

    Newman MEJ, Girvan M, Farmer JD. Optimal design, robustness, and risk aversion. Phys. Rev. Lett. 2002;89:028301.

    Not in our library10.1103/physrevlett.89.028301

64. 64.

    K. Ikehara, A. Clauset, Characterizing the structural diversity of complex networks across domains. https://arxiv.org/abs/1710.11304 (2017).

    Not in our library

65. 65.

    Barrat, A., Barthélemy, M. & Vespignani, A. Dynamical Processes on Complex Networks (Cambridge Univerity Press, Cambridge, UK, 2008).

    Not in our library

66. 66.

    Vespignani A. Modelling dynamical processes in complex socio-technical systems. Nat. Phys. 2012;8:32-39.

    Not in our library10.1038/nphys2160

67. 67.

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

    Not in our library10.1103/physreve.65.035108

68. 68.

    Newman MEJ, Park J. Why social networks are different from other types of networks. Phys. Rev. E. 2003;68:036122.

    Not in our library10.1103/physreve.68.036122

69. 69.

    Watts DJ, Strogatz SH. Collective dynamics of ‘small-world’ networks. Nature. 1998;393:440-442.

    Not in our library10.1038/30918

70. 70.

    Colizza V, Flammini A, Serrano MA, Vespignani A. Detecting rich-club ordering in complex networks. Nat. Phys. 2006;2:110-115.

    Not in our library10.1038/nphys209

71. 71.

    Girvan M, Newman MEJ. Community structure in social and biological networks. Proc. Natl Acad.Sci. USA. 2002;99:7821-7826.

    Not in our library10.1073/pnas.122653799

72. 72.

    Clauset A, Moore C, Newman MEJ. Hierarchical structure and the prediction of missing links in networks. Nature. 2008;453:98-101.

    Not in our library10.1038/nature06830

73. 73.

    Milo R, et al. Superfamilies of evolved and designed networks. Science. 2004;303:1538-1542.

    Not in our library10.1126/science.1089167

74. 74.
    Classes of small-world networks · 2000

    Not checked
75. 75.

    Buzsáki G, Mizuseki K. The log-dynamic brain: how skewed distributions affect network operations. Nat. Rev. Neurosci. 2014;15:264-278.

    Not in our library10.1038/nrn3687

76. 76.

    Jeong H, Mason SP, Barabási AL, Oltvai ZN. Lethality and centrality in protein networks. Nature. 2001;411:41-42.

    Not in our library10.1038/35075138

77. 77.

    Malevergne Y, Pisarenko VF, Sornette D. Empirical distributions of log-returns: between the stretched exponential and the power law? Quant. Financ. 2005;5:379-401.

    Not in our library10.1080/14697680500151343

78. 78.

    DuBois T, Eubank S, Srinivasans A. The effect of random edge removal on network degree sequence. Electron. J. Comb. 2012;19:1-20.

    Not in our library

79. 79.

    Easley, D. & Kleinberg, J. Networks, Crowds, and Markets: Reasoning about a Highly Connected World (Cambridge University Press, Cambridge, UK, 2010).

    Not in our library

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.