- Physical Review Journals
All JournalsPhysics Magazine

Physical Review Research

Reuse & Permissions

It is not necessary to obtain permission to reuse this article or its components as it is available under the terms of the Creative Commons Attribution 4.0 International license. This license permits unrestricted use, distribution, and reproduction in any medium, provided attribution to the author(s) and the published article's title, journal citation, and DOI are maintained. Please note that some figures may have been included with permission from other third parties. It is your responsibility to obtain the proper permission from the rights holder directly for these figures.

Export citation

Export citation

Choose format for download:

Download Citation
  • Open Access

Identifying time dependence in network growth

Max Falkenberg1,2,*, Jong-Hyeok Lee3, Shun-ichi Amano3, Ken-ichiro Ogawa3, Kazuo Yano4, Yoshihiro Miyake3, Tim S. Evans1,2, and Kim Christensen1,2

  • 1Blackett Laboratory, Imperial College London, London SW7 2AZ, United Kingdom
  • 2Centre for Complexity Science, Imperial College London, London SW7 2AZ, United Kingdom
  • 3Department of Computer Science, Tokyo Institute of Technology, Yokohama, Kanagawa 226-0027, Japan
  • 4Center Research Laboratory, Hitachi Ltd., Kokubunji, Tokyo 185-8601, Japan

  • *Corresponding author: max.falkenberg13@imperial.ac.uk
PDF

Phys. Rev. Research 2, 023352 – Published 18 June, 2020

DOI: https://doi.org/10.1103/PhysRevResearch.2.023352

Abstract

Identifying power-law scaling in real networks—indicative of preferential attachment—has proved controversial. Critics argue that measuring the temporal evolution of a network directly is better than measuring the degree distribution when looking for preferential attachment. However, many of the established methods do not account for any potential time dependence in the attachment kernels of growing networks, or methods assume that node degree is the key observable determining network evolution. In this paper, we argue that these assumptions may lead to misleading conclusions about the evolution of growing networks. We illustrate this by introducing a simple adaptation of the Barabási-Albert model, the “k2 model,” where new nodes attach to nodes in the existing network in proportion to the number of nodes one or two steps from the target node. The k2 model results in time dependent degree distributions and attachment kernels, despite initially appearing to grow as linear preferential attachment, and without the need to include explicit time dependence in key network parameters (such as the average out-degree). We show that similar effects are seen in several real world networks where constant network growth rules do not describe their evolution. This implies that measurements of specific degree distributions in real networks are likely to change over time.

View figure in article

Physics Subject Headings (PhySH)

Article Text

References (83)

  1. V. Vasiliauskaite and F. E. Rosas, Understanding complexity via network theory: a gentle introduction, arXiv:2004.14845.
  2. D. J. Watts and S. H. Strogatz, Collective dynamics of ‘small-world’ networks, Nature (London) 393, 440 (1998).
  3. D. S. Price, A general theory of bibliometric and other cumulative advantage processes, J. Am. Soc. Inf. Sci. 27, 292 (1976).
  4. A.-L. Barabási and R. Albert, Emergence of scaling in random networks, Science 286, 509 (1999).
  5. A. D. Broido and A. Clauset, Scale-free networks are rare, Nat. Commun. 10, 1017 (2019).
  6. M. E. Newman, Power laws, pareto distributions and zipf's law, Contemp. Phys. 46, 323 (2005).
  7. R. Albert, H. Jeong, and A.-L. Barabási, Diameter of the World-Wide Web, Nature (London) 401, 130 (1999).
  8. S. Redner, How popular is your paper? an empirical study of the citation distribution, Eur. Phys. J. B 4, 131 (1998).
  9. R. F. i Cancho and R. V. Solé, The small world of human language, Proc. R. Soc. London B 268, 2261 (2001).
  10. F. Liljeros, C. R. Edling, L. A. N. Amaral, H. E. Stanley, and Y. Åberg, The web of human sexual contacts, Nature (London) 411, 907 (2001).
  11. A. Java, X. Song, T. Finin, and B. Tseng, Why we twitter: understanding microblogging usage and communities, in Proceedings of the 9th WebKDD and 1st SNA-KDD 2007 workshop on Web mining and social network analysis (ACM, San Jose, California, 2007), pp. 56–65.
  12. R. Cohen and S. Havlin, Scale-Free Networks Are Ultrasmall, Phys. Rev. Lett. 90, 058701 (2003).
  13. P. Crucitti, V. Latora, M. Marchiori, and A. Rapisarda, Efficiency of scale-free networks: error and attack tolerance, Phys. A (Amsterdam, Neth.) 320, 622 (2003).
  14. P. Holme, Rare and everywhere: Perspectives on scale-free networks, Nat. Commun. 10, 1016 (2019).
  15. A. Clauset, C. R. Shalizi, and M. E. Newman, Power-law distributions in empirical data, SIAM Rev. 51, 661 (2009).
  16. F. Radicchi, S. Fortunato, and C. Castellano, Universality of citation distributions: Toward an objective measure of scientific impact, Proc. Natl. Acad. Sci. U.S.A. 105, 17268 (2008).
  17. G. Lima-Mendez and J. van Helden, The powerful law of the power law and other myths in network biology, Mol. BioSyst. 5, 1482 (2009).
  18. W. Willinger, D. Alderson, and J. C. Doyle, Mathematics and the internet: A source of enormous confusion and great potential, Notices of the American Mathematical Society 56, 586 (2009).
  19. M. Golosovsky, Power-law citation distributions are not scale-free, Phys. Rev. E 96, 032306 (2017).
  20. M. P. Stumpf and M. A. Porter, Critical truths about power laws, Science 335, 665 (2012).
  21. I. Sendiña-Nadal, M. M. Danziger, Z. Wang, S. Havlin, and S. Boccaletti, Assortativity and leadership emerge from anti-preferential attachment in heterogeneous networks, Sci. Rep. 6, 21297 (2016).
  22. A. M. Kang, Connectivity in biological networks: Are they really scale-free? Network Biology (2020).
  23. K.-I. Goh, E. Oh, H. Jeong, B. Kahng, and D. Kim, Classification of scale-free networks, Proc. Natl. Acad. Sci. U.S.A. 99, 12583 (2002).
  24. T. House, J. M. Read, L. Danon, and M. J. Keeling, Testing the hypothesis of preferential attachment in social network formation, EPJ Data Science 4, 13 (2015).
  25. A.-L. Barabási et al., Network science (Cambridge University Press, Cambridge, UK, 2016).
  26. I. Voitalov, P. van der Hoorn, R. van der Hofstad, and D. Krioukov, Scale-free networks well done, Phys. Rev. Research 1, 033034 (2019).
  27. M. Gerlach and E. G. Altmann, Testing Statistical Laws in Complex Systems, Phys. Rev. Lett. 122, 168301 (2019).
  28. I. Z. Kiss, D. M. Green, and R. R. Kao, The effect of network mixing patterns on epidemic dynamics and the efficacy of disease contact tracing, J. R. Soc., Interface 5, 791 (2008).
  29. M. Piraveenan, M. Prokopenko, and A. Zomaya, Assortative mixing in directed biological networks, IEEE/ACM Transactions on Computational Biology and Bioinformatics 9, 66 (2012).
  30. P. L. Krapivsky, S. Redner, and F. Leyvraz, Connectivity of Growing Random Networks, Phys. Rev. Lett. 85, 4629 (2000).
  31. P. Krapivsky and D. Krioukov, Scale-free networks as preasymptotic regimes of superlinear preferential attachment, Phys. Rev. E 78, 026114 (2008).
  32. M. E. J. Newman, Clustering and preferential attachment in growing networks, Phys. Rev. E 64, 025102(R) (2001).
  33. H. Jeong, Z. Néda, and A.-L. Barabási, Measuring preferential attachment in evolving networks, Europhys. Lett. 61, 567 (2003).
  34. C. P. Massen and J. P. K. Doye, Preferential attachment during the evolution of a potential energy landscape, J. Chem. Phys. 127, 114306 (2007).
  35. V. Gómez, H. J. Kappen, and A. Kaltenbrunner, Modeling the structure and evolution of discussion cascades, in Proceedings of the 22Nd ACM Conference on Hypertext and Hypermedia, HT '11 (ACM, New York, 2011), pp. 181–190.
  36. P. Sheridan, Y. Yagahara, and H. Shimodaira, Measuring preferential attachment in growing networks with missing-timelines using markov chain monte carlo, Phys. A (Amsterdam, Neth.) 391, 5031 (2012).
  37. J. Kunegis, M. Blattner, and C. Moser, Preferential attachment in online networks: Measurement and explanations, in Proceedings of the 5th annual ACM web science conference (ACM, Paris, France, 2013), pp. 205–214.
  38. T. Pham, P. Sheridan, and H. Shimodaira, Pafit: A statistical method for measuring preferential attachment in temporal complex networks, PLoS One 10, e0137796 (2015).
  39. A. Herdağdelen, E. Aygün, and H. Bingol, A formal treatment of generalized preferential attachment and its empirical validation, Europhys. Lett. 78, 60007 (2007).
  40. J. Leskovec, J. Kleinberg, and C. Faloutsos, Graphs over time: densification laws, shrinking diameters and possible explanations, in Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining (ACM, Chicago, Illinois, 2005), pp. 177–187.
  41. G. A. Ronda-Pupo and T. Pham, The evolutions of the rich get richer and the fit get richer phenomena in scholarly networks: the case of the strategic management journal, Scientometrics 116, 363 (2018).
  42. P. Sheridan and T. Onodera, A preferential attachment paradox: How preferential attachment combines with growth to produce networks with log-normal in-degree distributions, Sci. Rep. 8, 2811 (2018).
  43. E. Eisenberg and E. Y. Levanon, Preferential Attachment in the Protein Network Evolution, Phys. Rev. Lett. 91, 138701 (2003).
  44. D. Kondor, M. Pósfai, I. Csabai, and G. Vattay, Do the rich get richer? an empirical analysis of the bitcoin transaction network, PLoS One 9, e86197 (2014).
  45. M. Perc, Evolution of the most common english words and phrases over the centuries, J. R. Soc., Interface 9, 3323 (2012).
  46. M. Szell and S. Thurner, Measuring social dynamics in a massive multiplayer online game, Social Networks 32, 313 (2010).
  47. W. Li, T. Aste, F. Caccioli, and G. Livan, Early coauthorship with top scientists predicts success in academic careers, Nat. Commun. 10, 5170 (2019).
  48. A. Vazquez, Knowing a network by walking on it: emergence of scaling (2000), arXiv:cond-mat/0006132.
  49. R. Lambiotte, P. L. Krapivsky, U. Bhat, and S. Redner, Structural Transitions in Densifying Networks, Phys. Rev. Lett. 117, 218301 (2016).
  50. U. Bhat, P. L. Krapivsky, R. Lambiotte, and S. Redner, Densification and structural transitions in networks that grow by node copying, Phys. Rev. E 94, 062302 (2016).
  51. P. L. Krapivsky and S. Redner, Network growth by copying, Phys. Rev. E 71, 036118 (2005).
  52. C. Dangalchev, Generation models for scale-free networks, Phys. A (Amsterdam, Neth.) 338, 659 (2004).
  53. S. Wang, X. Wang, Q. Song, and Y. Zhang, High-order degree and combined degree in complex networks, Mathematical Problems in Engineering 2018, 4925841 (2018).
  54. A. Topirceanu, M. Udrescu, and R. Marculescu, Weighted betweenness preferential attachment: A new mechanism explaining social network formation and evolution, Sci. Rep. 8, 10871 (2018).
  55. S.-i. Amano, K.-i. Ogawa, and Y. Miyake, Node property of weighted networks considering connectability to nodes within two degrees of separation, Sci. Rep. 8, 8464 (2018).
  56. A. E. Mislove, Online social networks: measurement, analysis, and applications to distributed information systems, Ph.D. thesis, Rice University, 2009.
  57. M. S. Granovetter, The strength of weak ties, in Social Networks (Elsevier, Cambridge, Massachusetts, 1977), pp. 347–367.
  58. R. S. Burt, Structural Holes: The Social Structure of Competition (Harvard University Press, Cambridge, Massachusetts, 1992).
  59. L. Katz, A new status index derived from sociometric index, Psychometrika 18, 39 (1953).
  60. M. Newman, Networks, 2nd ed. (OUP, Oxford, 2018).
  61. S. Brin and L. Page, The anatomy of a large-scale hypertextual web search engine, Computer networks and ISDN systems 30, 107 (1998).
  62. R. Toivonen, L. Kovanen, M. Kivelä, J.-P. Onnela, J. Saramäki, and K. Kaski, A comparative study of social network models: Network evolution models and nodal attribute models, Social Networks 31, 240 (2009).
  63. S. Goldberg, H. Anthony, and T. Evans, Modelling citation networks, Scientometrics 105, 1577 (2015).
  64. S. Ohno, Evolution by Gene Duplication (Springer Science & Business Media, Berlin, Heidelberg, 2013).
  65. I. Ispolatov, P. L. Krapivsky, and A. Yuryev, Duplication-divergence model of protein interaction network, Phys. Rev. E 71, 061911 (2005).
  66. J. Kim, P. L. Krapivsky, B. Kahng, and S. Redner, Infinite-order percolation and giant fluctuations in a protein interaction network, Phys. Rev. E 66, 055101(R) (2002).
  67. B. Viswanath, A. Mislove, M. Cha, and K. P. Gummadi, On the evolution of user interaction in facebook, in Proceedings of the 2nd ACM workshop on Online social networks (Association for Computing Machinery, Barcelona, Spain, 2009), pp. 37–42.
  68. American Physical Society, APS Data Sets for Research, https://journals.aps.org/datasets (2018).
  69. J. Kunegis, Konect: The koblenz network collection, in Proceedings of the 22nd International Conference on World Wide Web, WWW'13 Companion (Association for Computing Machinery, New York, 2013), pp. 1343–1350.
  70. A.-L. Barabási, H. Jeong, Z. Néda, E. Ravasz, A. Schubert, and T. Vicsek, Evolution of the social network of scientific collaborations, Phys. A (Amsterdam, Neth.) 311, 590 (2002).
  71. N. A. Arnold, R. J. Mondragon and R. G. Clegg, Changing the tune: mixtures of network models that vary in time (2019), arXiv:1909.13253.
  72. C. Knappett, T. Evans, and R. Rivers, Modelling maritime interaction in the aegean bronze age, Antiquity 82, 1009 (2008).
  73. D. S. Bassett and O. Sporns, Network neuroscience, Nat. Neurosci. 20, 353 (2017).
  74. F. Schweitzer, G. Fagiolo, D. Sornette, F. Vega-Redondo, A. Vespignani, and D. R. White, Economic networks: The new challenges, Science 325, 422 (2009).
  75. R. Pastor-Satorras, C. Castellano, P. Van Mieghem, and A. Vespignani, Epidemic processes in complex networks, Rev. Mod. Phys. 87, 925 (2015).
  76. P. L. Krapivsky and S. Redner, Organization of growing random networks, Phys. Rev. E 63, 066123 (2001).
  77. A. Vázquez, Growing networks with local rules: preferential attachment, clustering hierarchy and degree correlations, Phys. Rev. E 67, 056104 (2003).
  78. F. Chung, L. Lu, T. G. Dewey, and D. J. Galas, Duplication models for biological networks, J. Comput. Biol. 10, 677 (2003).
  79. J. Saramäki and K. Kaski, Scale-free networks generated by random walkers, Phys. A (Amsterdam, Neth.) 341, 80 (2004).
  80. T. S. Evans and J. P. Saramäki, Scale free networks from self-organisation, Phys. Rev. E 72, 026138 (2005).
  81. J. Sun, M. Medo, and S. Staab, Time-invariant degree growth in preferential attachment network models, Phys. Rev. E 101, 022309 (2020).
  82. V. Amati, A. Lomi, and D. Mascia, Some days are better than others: Examining time-specific variation in the structuring of interorganizational relations, Social Networks 57, 18 (2019).
  83. https://github.com/MaxFalkenberg/k2model.

Outline

Information

Phys. Rev. Research 2, 023352– Published 18 June, 2020
  • Received 24 January 2020
  • Accepted 14 May 2020
Crossmark - Check for updates button
Creative Commons Logo

Published by the American Physical Society under the terms of the Creative Commons Attribution 4.0 International license. Further distribution of this work must maintain attribution to the author(s) and the published article's title, journal citation, and DOI.

Published by the American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation