Multilevel Compression of Random Walks on Networks Reveals Hierarchical Organization in Large Integrated Systems

Abstract

To comprehend the hierarchical organization of large integrated systems, we introduce the hierarchical map equation, which reveals multilevel structures in networks. In this information-theoretic approach, we exploit the duality between compression and pattern detection; by compressing a description of a random walker as a proxy for real flow on a network, we find regularities in the network that induce this system-wide flow. Finding the shortest multilevel description of the random walker therefore gives us the best hierarchical clustering of the network--the optimal number of levels and modular partition at each level--with respect to the dynamics on the network. With a novel search algorithm, we extract and illustrate the rich multilevel organization of several large social and biological networks. For example, from the global air traffic network we uncover countries and continents, and from the pattern of scientific communication we reveal more than 100 scientific fields organized in four major disciplines: life sciences, physical sciences, ecology and earth sciences, and social sciences. In general, we find shallow hierarchical structures in globally interconnected systems, such as neural networks, and rich multilevel organizations in systems with highly separated regions, such as road networks.

Full text

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

References 32

1. 1.

   Albert R, Barabási A. Statistical mechanics of complex networks. Rev Mod Phys. 2002;74:47-97.

   Not in our library

2. 2.

   Newman MEJ. The structure and function of complex networks. SIAM Review. 2003;45:167-256.

   Not in our library

3. 3.

   Fortunato S. Community detection in graphs. Phys Rep. 2010;486:75-174.

   Not in our library

4. 4.

   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

5. 5.

   Ahn YY, Bagrow JP, Lehmann S. Link communities reveal multiscale complexity in networks. Nature. 2010;466:761-764.

   Not in our library10.1038/nature09182

6. 6.

   Winther R. Varieties of modules: kinds, levels, origins, and behaviors. Journal of Experimental Zoology Part B: Molecular and Developmental Evolution. 2001;291:116-129.

   Not in our library10.1002/jez.1064

7. 7.

   Schlosser G, Wagner G. Modularity in development and evolution. 2004.

   Not in our library

8. 8.

   Ravasz E, Barabási A. Hierarchical organization in complex networks. Physical Review E. 2003;67:26112.

   Not in our library10.1103/physreve.67.026112

9. 9.

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

   Not in our library10.1038/nature06830

10. 10.

    Sales-Pardo M, Guimer R, Moreira AA, Amaral LAN. Extracting the hierarchical organization of complex systems. Proc Natl Acad Sci USA. 2007;104:15224.

    Not in our library10.1073/pnas.0703740104

11. 11.

    Ronhovde P, Nussinov Z. Multiresolution community detection for megascale networks by information-based replica correlations. Physical Review E. 2009;80:16109.

    Not in our library10.1103/physreve.80.016109

12. 12.

    Kovacs I, Palotai R, Szalay M, Csermely P. Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics. PloS one. 2010;5:e12528.

    Not in our library10.1371/journal.pone.0012528

13. 13.

    Müller-Linow M, Hilgetag CC, Hütt MT. Organization of excitable dynamics in hierarchical biological networks. Plos Comput Biol. 2008;4:e1000190.

    Not in our library10.1371/journal.pcbi.1000190

14. 14.

    Rosvall M, Bergstrom C. Maps of information ow reveal community structure in complex networks. Proc Natl Acad Sci USA. 2008;105:1118-1123.

    Not in our library10.1073/pnas.0706851105

15. 15.

    Rosvall M, Axelsson D, Bergstrom C. The map equation. Eur Phys J Special Topics. 2009;178:13-23.

    Not in our library

16. 16.

    Rissanen J. Modeling by shortest data description. Automatica. 1978;14:465-471.

    Not in our library

17. 17.

    Grünwald P, Myung IJ, Pitt M. Advances in minimum description length: theory and applications. 2005.

    Not in our library

18. 18.

    Shannon CE. A mathematical theory of communication. Bell Labs Tech J. 1948;27:379-423.

    Not in our library

19. 19.

    Lancichinetti A, Fortunato S. Community detection algorithms: A comparative analysis. Phys Rev E. 2009;80:056117.

    Not in our library10.1103/physreve.80.056117

20. 20.
    Mapping Change in Large Networks · 2010

    No notice
21. 21.

    Guimera R, Mossa S, Turtschi A, Amaral L. The worldwide air transportation network: Anomalous centrality, community structure, and cities' global roles. Proc Natl Acad Sci USA. 2005;102:7794.

    Not in our library10.1073/pnas.0407994102

22. 22.

    Goh K, Cusick M, Valle D, Childs B, Vidal M, et al. The human disease network. Proc Natl Acad Sci USA. 2007;104:8685.

    Not in our library10.1073/pnas.0701361104

23. 23.

    Watts D, Strogatz S. Collective dynamics of small-worldnetworks. Nature. 1998;393:440-442.

    Not in our library10.1038/30918

24. 24.

    We have compiled the network from the Airline Origin and Destination Survey (DB1B) made public by The Research and Innovative Technology Administration (RITA). 2007.

    Not in our library

25. 25.

    Rosvall M. 2010.

    Not in our library

26. 26.

    Clauset A, Newman MEJ, Moore C. Finding community structure in very large networks. Phys Rev E. 2004;70:066111.

    Not in our library10.1103/physreve.70.066111

27. 27.

    Wakita K, Tsurumi T. Finding community structure in mega-scale social networks. 2007.

    Not in our library

28. 28.

    Blondel V, Guillaume J, Lambiotte R, Mech E. Fast unfolding of communities in large networks. J Stat Mech: Theory Exp. 2008;2008:P10008.

    Not in our library

29. 29.

    Danon L, Díaz-Guilera A, Duch J, Arenas A. Comparing community structure identification. J Stat Mech. 2005;P09008.

    Not in our library

30. 30.

    Leskovec J, Lang K, Dasgupta A, Mahoney M. Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters. Internet Math. 2009;Volume 6:29-123.

    Not in our library

31. 31.

    We have compiled the call graph from the cross-platform library GLib, the coauthorship network from the references in refs. 1–3, and the political blogs from data provided by Twingly.com

    Not in our library

32. 32.

    Rosvall M, Trusina A, Minnhagen P, Sneppen K. Networks and cities: An information perspective. Phys Rev Lett. 2005;94:28701.

    Not in our library10.1103/physrevlett.94.028701

Cited by papers we hold 7

• Brain networks, dimensionality, and global signal averaging in resting-state fMRI: Hierarchical network structure results in low-dimensional spatiotemporal dynamics · 2020
  Not checked
• Cryptic inoviruses revealed as pervasive in bacteria and archaea across Earth’s biomes · 2019
  Corrected
• Tie-formation process within the communities of the Japanese production network: application of an exponential random graph model · 2019
  Not checked
• A side-effect free method for identifying cancer drug targets · 2018
  Not checked
• Correlations between community structure and link formation in complex networks. · 2013
  Not checked
• The Role of Gender in Scholarly Authorship · 2013
  No notice
• Finding Statistically Significant Communities in Networks · 2011
  No notice

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.