- 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

Hierarchical route to the emergence of leader nodes in real-world networks

Joseph D. O'Brien1, Kleber A. Oliveira1, James P. Gleeson1, and Malbor Asllani1,2

  • 1MACSI, Department of Mathematics and Statistics, University of Limerick, Limerick V94 T9PX, Ireland
  • 2School of Mathematics and Statistics, University College Dublin, Belfield, Dublin 4, Ireland

PDF

Phys. Rev. Research 3, 023117 – Published 14 May, 2021

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

Abstract

A large number of complex systems, naturally emerging in various domains, are well described by directed networks, resulting in numerous interesting features that are absent from their undirected counterparts. Among these properties is a strong non-normality, inherited by a strong asymmetry that characterizes such systems and guides their underlying hierarchy. In this work, we consider an extensive collection of empirical networks and analyze their structural properties using information-theoretic tools. A ubiquitous feature is observed amongst such systems as the level of non-normality increases. When the non-normality reaches a given threshold, highly directed substructures aiming towards terminal (sink or source) nodes, denoted here as leaders, spontaneously emerge. Furthermore, the relative number of leader nodes describe the level of anarchy that characterizes the networked systems. Based on the structural analysis, we develop a null model to capture features such as the aforementioned transition in the networks' ensemble. We also demonstrate that the role of leader nodes at the pinnacle of the hierarchy is crucial in driving dynamical processes in these systems. This work paves the way for a deeper understanding of the architecture of empirical complex systems and the processes taking place on them.

View figure in article

Physics Subject Headings (PhySH)

Article Text

References (112)

  1. M. Newman, Networks: An Introduction (Oxford university Press, Oxford, 2010).
  2. S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, and D. U. Hwang, Phys. Rep. 424, 175 (2006).
  3. S. Johnson and N. S. Jones, Proc. Natl. Acad. Sci. USA 114, 5618 (2017).
  4. S. Johnson, J. Phys. Complexity 1, 015003 (2020).
  5. M. Kawakatsu, P. S. Chodrow, N. Eikmeier, and D. B. Larremore, Proc. Natl. Acad. Sci. USA 118, e2015188118 (2021).
  6. M. Asllani, R. Lambiotte, and T. Carletti, Sci. Adv. 4, eaau9403 (2018).
  7. M. Asllani and T. Carletti, Phys. Rev. E 97, 042302 (2018).
  8. L. N. Trefethen and M. Embree, Spectra and Pseudospectra (Princeton University Press, Princeton, NJ, 2020).
  9. M. G. Neubert and H. Caswell, Ecology 78, 653 (1997).
  10. B. Ravoori, A. B. Cohen, J. Sun, A. E. Motter, T. E. Murphy, and R. Roy, Phys. Rev. Lett. 107, 034102 (2011).
  11. G. Hennequin, T. P. Vogels, and W. Gerstner, Phys. Rev. E 86, 011909 (2012).
  12. C. Pilgrim, W. Guo, and S. Johnson, Sci. Rep. 10, 4388 (2020).
  13. R. Muolo, M. Asllani, D. Fanelli, P. K. Maini, and T. Carletti, J. Theor. Biol. 480, 81 (2019).
  14. S. Nicoletti, D. Fanelli, N. Zagli, M. Asllani, G. Battistelli, T. Carletti, L. Chisci, G. Innocenti, and R. Livi, Chaos 29, 083123 (2019).
  15. R. Muolo, T. Carletti, J. P. Gleeson, and M. Asllani, Entropy 23, 36 (2021).
  16. G. Baggio, V. Rutten, G. Hennequin, and S. Zampieri, Sci. Adv. 6, eaba2282 (2020).
  17. T. M. Cover and J. A. Thomas, Elements of Information Theory (Wiley, New York, 2005).
  18. J. Gómez-Gardenes and V. Latora, Phys. Rev. E 78, 065102(R) (2008).
  19. T. Carletti, M. Asllani, D. Fanelli, and V. Latora, Phys. Rev. Research 2, 033012 (2020).
  20. D. J. De Solla Price, Science 149, 510 (1965).
  21. W. C. Allee and E. S. Bowen, J. Exp. Zool. 61, 185 (1932).
  22. N. Masuda, M. A. Porter, and R. Lambiotte, Phys. Rep. 716-717, 1 (2017).
  23. An exemption occurs when each node of the terminal SCC has a single outgoing edge, namely forms a closed directed path. Network motifs such as closed directed paths are very rare in real-world networks [110] mainly due to the inherent directedness of real networks [111].
  24. A. K. Jain, Patt. Rec. Lett. 31, 651 (2010).
  25. Pajek datasets, http://vlado.fmf.uni-lj.si/pub/networks/.
  26. J. Kunegis, The KONECT project, http://konect.cc/.
  27. H. Salgado, M. Peralta-Gil, S. Gama-Castro, A. Santos-Zavaleta, L. Muñiz-Rascado, J. S. García-Sotelo, V. Weiss, H. Solano-Lira, I. Martínez-Flores, A. Medina-Rivera, G. Salgado-Osorio, S. Alquicira-Hernández, K. Alquicira-Hernández, A. López-Fuentes, L. Porrón-Sotelo, A. M. Huerta, C. Bonavides-Martínez, Y. I. Balderas-Martínez, L. Pannier, M. Olvera et al., Nucl. Acids Res. 41, D203 (2013).
  28. V. Colizza, A. Flammini, M. A. Serrano, and A. Vespignani, Nat. Phys. 2, 110 (2006).
  29. A. L. Barabási and R. Albert, Science 286, 509 (1999).
  30. G. Bianconi and A. L. Barabási, Europhys. Lett. 54, 436 (2001).
  31. Y. Takahata, The Monkeys of Arashiyama: Thirty-five Years of Research in Japan and the West, edited by L. M. Fedigan, and P. J. Asquith (SUNY Press, Albany, 1991), pp. 123–139.
  32. R. V. Solé, S. C. Manrubia, B. Luque, J. Delgado, and J. Bascompte, Complexity 1, 13 (1996).
  33. E. Bonabeau, G. Theraulaz, and J.-L. Deneubourg, Physica A 217, 373 (1995).
  34. E. Bonabeau, G. Theraulaz, and J.-L. Deneubourg, Bull. Math. Biol. 58, 661 (1996).
  35. Z. Burda, J. Duda, J. M. Luck, and B. Waclaw, Phys. Rev. Lett. 102, 160602 (2009).
  36. D. Thieffry, A. M. Huerta, E. Pérez-Rueda, and J. Collado- Vides, Bioessays 20, 433 (1998).
  37. M. B. Gerstein, A. Kundaje, M. Hariharan, S. G. Landt, K.-K. Yan, C. Cheng, X. J. Mu, E. Khurana, J. Rozowsky, R. Alexander et al., Nature (London) 489, 91 (2012).
  38. C. T. Harbison, D. B. Gordon, T. I. Lee, N. K. Rinaldi, K. D. Macisaac, T. W. Danford, N. M. Hannett, J.-B. Tagne, D. B. Reynolds, J. Yoo, E. G. Jennings, J. Zeitlinger, D. K. Pokholok, M. Kellis, P. A. Rolfe, K. T. Takusagawa, E. S. Lander, D. K. Gifford, E. Fraenkel, and R. A. Young, Nature (London) 431, 99 (2004).
  39. M. C. Costanzo, M. E. Crawford, J. E. Hirschman, J. E. Kranz, P. Olsen, L. S. Robertson, M. S. Skrzypek, B. R. Braun, K. L. Hopkins, P. Kondu et al., Nucl. Acids Res. 29, 75 (2001).
  40. J. Sanz, J. Navarro, A. Arbués, C. Martín, P. C. Marijuán, and Y. Moreno, PLoS ONE 6, e22178 (2011).
  41. R. M. Ewing, P. Chu, F. Elisma, H. Li, P. Taylor, S. Climie, L. McBroom-Cerajewski, M. D. Robinson, L. O'Connor, M. Li, et al., Mol. Syst. Biol. 3, 89 (2007).
  42. E. Galán-Vásquez, B. Luna, and A. Martínez-Antonio, Microb. Informatics Exp. 1, 3 (2011).
  43. N. T. Markov, M. Ercsey-Ravasz, C. Lamy, A. R. R. Gomes, L. Magrou, P. Misery, P. Giroud, P. Barone, C. Dehay, Z. Toroczkai et al., Proc. Natl. Acad. Sci. USA 110, 5187 (2013).
  44. D. J. Watts and S. H. Strogatz, Nature (London) 393, 440 (1998).
  45. M. Kaiser and C. C. Hilgetag, PLoS Comput. Biol. 2, e95 (2006).
  46. M. Bota and L. W. Swanson, J. Comp. Neurol. 500, 807 (2007).
  47. C. Carere, G. F. Ball, and J. Balthazart, J. Comp. Neurol. 500, 894 (2007).
  48. R. M. Cowell, K. R. Blake, and J. W. Russell, J. Comp. Neurol. 502, 1 (2007).
  49. L. Harriger, M. P. Van Den Heuvel, and O. Sporns, PLoS ONE 7, e46497 (2012).
  50. H. Jeong, B. Tombor, R. Albert, Z. N. Oltvai, and A.-L. Barabási, Nature (London) 407, 651 (2000).
  51. S. Johnson, Network data repository from various sources https://www.samuel-johnson.org/data.
  52. M. A. de Reus and M. P. van den Heuvel, J. Neurosci. 33, 12929 (2013).
  53. R. M. Thompson and C. Townsend, Ecology 84, 145 (2003).
  54. R. M. Thompson and A. R. Mcintosh, Ecol Lett. 1, 200 (1998).
  55. J. Klaise and S. Johnson, Sci. Rep. 7, 16197 (2017).
  56. J. A. Dunne, K. D. Lafferty, A. P. Dobson, R. F. Hechinger, A. M. Kuris, N. D. Martinez, J. P. McLaughlin, K. N. Mouritsen, R. Poulin, K. Reise et al., PLoS Biol. 11, e1001579 (2013).
  57. R. M. Thompson and C. Townsend, Oikos 108, 137 (2005).
  58. J. Memmott, N. D. Martinez, and J. Cohen, J. Anim. Ecol. 69, 1 (2000).
  59. J. Bascompte, C. J. Melián, and E. Sala, Proc. Natl. Acad. Sci. USA 102, 5443 (2005).
  60. R. E. Ulanowicz and D. Baird, J. Marine Syst. 19, 159 (1999).
  61. B. J. Cole, Science 212, 83 (1981).
  62. T. Grant, Anim. Behav. 21, 449 (1973).
  63. R. R. Christian and J. J. Luczkovich, Ecol. Modell. 117, 99 (1999).
  64. L. Goldwasser and J. Roughgarden, Ecology 74, 1216 (1993).
  65. M. Huxham, S. Beaney, and D. Raffaelli, Oikos 76, 284 (1996).
  66. A. Eklöf, U. Jacob, J. Kopp, J. Bosch, R. Castro-Urgal, N. P. Chacoff, B. Dalsgaard, C. de Sassi, M. Galetti, P. R. Guimarães et al., Ecol. Lett. 16, 577 (2013).
  67. J. A. Dunne, R. J. Williams, N. D. Martinez, R. A. Wood, and D. H. Erwin, PLoS Biol. 6, e102 (2008).
  68. K. Havens, Science 257, 1107 (1992).
  69. J. A. van Hooff and J. A. B. Wensing, in Man and Wolf: Advances, Issues, and Problems in Captive Wolf Research, edited by H. Frank (Springer Science & Business Media, 1987), pp. 219–252.
  70. N. D. Martinez, Ecol. Monogr. 61, 367 (1991).
  71. J. Link, Mar. Ecol.: Prog. Ser. 230, 1 (2002).
  72. F. F. Strayer and M. S. Cummins, Dominance Relations: An Ethological View of Human Conflict and Social Interaction (Livingstone, Edinburgh, 1980).
  73. P. H. Warren, Oikos 55, 299 (1989).
  74. P. Yodzis, J. Anim. Ecol. 67, 635 (1998).
  75. R. Ulanowicz and D. L. DeAngelis, Network analysis of trophic dynamics in South Florida ecosystems, U.S. Geological Survey Programon the South Florida Ecosystem; Proceedings of South Florida Restoration ScienceForum, May 17–19, 1999, Boca Raton, Florida, edited by S. Gerould and A. Higher (BiblioGov, 1999), pp. 114–115.
  76. T. Clutton-Brock, P. Greenwood, and R. Powell, Z. Tierpsychol. 41, 202 (1976).
  77. M. W. Schein and M. H. Fohrman, Brit. J. Anim. Behav. 3, 45 (1955).
  78. C. C. Hass, J. Zool. 225, 509 (1991).
  79. A. Guhl, Trans. Kans. Acad. Sci. (1903) 71, 379 (1968).
  80. D. F. Lott, Z. Tierpsychol. 49, 418 (1979).
  81. M. J. Bashaw, M. A. Bloomsmith, T. L. Maple, and F. B. Bercovitch, J. Comp. Psych. 121, 46 (2007).
  82. V. Krebs, Madoff feeder funds. http://www.thenetworkthinkers.com/2009/02/madoff-feeder-funds.html.
  83. M. Flandreau and C. Jobst, J. Econ. History 65, 977 (2005).
  84. M. De Domenico, V. Nicosia, A. Arenas, and V. Latora, Nat. Commun. 6, 6864 (2015).
  85. D. A. Smith and D. R. White, Soc. Forces 70, 857 (1992).
  86. W. De Nooy, A. Mrvar, and V. Batagelj, Exploratory Social Network Analysis with Pajek: Revised and Expanded Edition for Updated Software (Cambridge University Press, Cambridge, 2018), Vol. 46.
  87. E. Garfield, Index of citation networks produced by analyses from the software HistCite, http://www.garfield.library.upenn.edu/histcomp/index.html.
  88. N. P. Hummon and P. Dereian, Soc. Networks 11, 39 (1989).
  89. A. Schubert, Scientometrics 53, 3 (2002).
  90. M. Ley, in International Symposium on String Processing and Information Retrieval (Springer, Berlin, 2002), pp. 1–10.
  91. R. Milo, S. Itzkovitz, N. Kashtan, R. Levitt, S. Shen-Orr, I. Ayzenshtat, M. Sheffer, and U. Alon, Science 303, 1538 (2004).
  92. W. De Nooy, Poetics 26, 385 (1999).
  93. B. R. da Cunha, P. MacCarron, J. F. Passold, L. W. dos Santos, K. A. Oliveira, and J. P. Gleeson, Sci. Rep. 10, 73 (2020).
  94. D. L. Linvill and P. L. Warren, Political Commun. 37, 447 (2020).
  95. J. Leskovec, D. Huttenlocher, and J. Kleinberg, Signed Networks in Social Media (ACM Press, New York, NY, 2010).
  96. L. A. Adamic and N. Glance, The Political Blogosphere and the 2004 U.S. Election: Divided They Blog (ACM Press, New York, NY, 2005).
  97. Kaggle, Chess ratings - elo versus the rest of the world (2010), https://www.kaggle.com/c/chess/data.
  98. J. Coleman, E. Katz, and H. Menzel, Sociometry 20, 253 (1957).
  99. J. Kunegis, DNC emails co-recipients. KONECT, the Koblenz Network Collection (2016), https://networks.skewed.de/net/dnc.
  100. T. Opsahl and P. Panzarasa, Social Networks 31, 155 (2009).
  101. T. N. for Research Core Team, Transportation networks for research, https://github.com/bstabler/TransportationNetworks.
  102. U. S. F. A. Administration, Air traffic control system command center extracted prior to 2010, https://www.fly.faa.gov/.
  103. L. J. LeBlanc, E. K. Morlok, and W. P. Pierskalla, Trans. Res. 9, 309 (1975).
  104. T. Opsahl, F. Agneessens, and J. Skvoretz, Soc. Networks 32, 245 (2010).
  105. F. Munoz-Mendez, K. Han, K. Klemmer, and S. Jarvis, Community Structures, Interactions and Dynamics in London's Bicycle Sharing Network (ACM Press, New York, NY, 2018).
  106. C. Demetrescu, 9th dimacs implementation challenge - shortest paths, http://archive.dimacs.rutgers.edu/Workshops/Challenge9/.
  107. M. J. Williams and M. Musolesi, R. Soc. Open Sci. 3, 160196 (2016).
  108. OpenFlights, Airport, airline and route data, https://openflights.org/data.html.
  109. J. Zhang, S. Pourazarm, C. G. Cassandras, and I. C. Paschalidis, in Proceedings of the 2016 IEEE 55th Conference on Decision and Control (CDC) (IEEE, New York, 2016), pp. 789–794.
  110. R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon, Science 298, 824 (2002).
  111. V. Domínguez-García, S. Pigolotti, and M. A. Muñoz, Sci. Rep. 4, 7497 (2014).
  112. Please see https://icon.colorado.edu and https://networks.skewed.de.

Outline

Information

Phys. Rev. Research 3, 023117– Published 14 May, 2021
  • Received 16 December 2020
  • Accepted 12 April 2021
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