Multilevel Compression of Random Walks on Networks Reveals Hierarchical Organization in Large Integrated Systems
Open Access
- 8 April 2011
- journal article
- research article
- Published by Public Library of Science (PLoS) in PLOS ONE
- Vol. 6 (4), e18209
- https://doi.org/10.1371/journal.pone.0018209
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.Other Versions
This publication has 28 references indexed in Scilit:
- Link communities reveal multiscale complexity in networksNature, 2010
- Community detection in graphsPhysics Reports, 2009
- Hierarchical structure and the prediction of missing links in networksNature, 2008
- Extracting the hierarchical organization of complex systemsProceedings of the National Academy of Sciences of the United States of America, 2007
- Hierarchical organization in complex networksPhysical Review E, 2003
- The Structure and Function of Complex NetworksSIAM Review, 2003
- Community structure in social and biological networksProceedings of the National Academy of Sciences of the United States of America, 2002
- Statistical mechanics of complex networksReviews of Modern Physics, 2002
- Varieties of modules: Kinds, levels, origins, and behaviorsJournal of Experimental Zoology, 2001
- Modularity in development and evolutionBioEssays, 2000