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

By Martin Rosvall, Carl T. Bergstrom. PLoS ONE, 2010

419 citations recorded by the source corpus.

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.

Subfields: Economics and Econometrics, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/2414202fed2bca9417c6e10539150cb302506672

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Economics and Econometrics

In Statistical and Nonlinear Physics

Citations in the corpus

A new methodology for constructing a publication-level classification system of science (2012, background): “…have been working on developing their own classification systems (Archambault, Beauchesne, & Caruso, 2011; Glänzel & Schubert, 2003; Klavans & Boyack, 2010) or on testing techniques that can be used to construct such systems (e.g., Rafols & Leydesdorff, 2009; Rosvall & Bergstrom, 2008, 2011).”
Community detection in networks: A user guide (2016, background): “It has been successively extended to the detection of hierarchical community structure (Rosvall and Bergstrom, 2011) and of overlapping clusters (Viamontes Esquivel and Rosvall, 2011).”
Local Modeling of Attributed Graphs: Algorithms and Applications (2016, background): “Multiscale Community Detection Many techniques for detecting multiple scales of discrete communities in graphs have been proposed [1, 73, 122].”
Communities, modules and large-scale structure in networks (2011, neutral): “A different class of methods are those based on information-theoretic ideas, such as the minimum-description-length methods of Rosvall and Bergstrom 26,43 and related methods based on statistical inference, such as the message-passing method of Hastings 25 .”
Random walks and diffusion on networks (2016, methodology): “torial Laplacian matrix L[360]. 5.3.3. InfoMap InfoMap is another algorithm for community detection based on RWs [361]. It is very popular and has been extended to the case of hierarchical algorithms [362], memory networks [250], and multilayer networks [235]. In this section, we discuss the basic v”
Structure and dynamics of molecular networks: A novel paradigm of drug discovery: A comprehensive review (2012, methodology): “The hierarchical map approach of Rosvall and Bergstrom (2011) used the shortestmulti-level description of a random walk (http://www.tp.umu.se/~rosvall/code.html).”
Finding Statistically Significant Communities in Networks (2010, neutral): “We compare OSLOM with a recent extension of Infomap to networks with hierarchical community structure [56].”
Hierarchical block structures and high-resolution model selection in large networks (2013, methodology): “We concentrate on two methods which have been reported to provide good results in synthetic benchmarks [91], namely the Lou-vain method [12], based on modularity optimization, and the Infomod method [45, 92, 93], based on compression of random walks.”
Measuring Scholarly Impact (2014, background): “One strength of the map equation framework is that it is generalizable to higher-order structures, for example to hierarchical structures (Rosvall & Bergstrom, 2011), overlapping structures (Esquivel & Rosvall, 2011), or higher-order Markov dynamics (Rosvall et al., 2013).”
Don't Walk, Skip!: Online Learning of Multi-scale Network Embeddings (2016, background): “Multiscale Community Detection Many techniques for detecting multiple scales of discrete communities in graphs have been proposed [16]–[18].”
Men Set Their Own Cites High: Gender and Self-citation across Fields and over Time (2016, background): “To provide more context for the importance of self-citation, we wanted to know what proportion of citations in an article are self-citations, on average.”