The map equation
By Martin Rosvall, D. Axelsson, Carl T. Bergstrom. 2009
920 citations recorded by the source corpus.
Abstract Many real-world networks are so large that we must simplify their structure before we can extract useful information about the systems they represent. As the tools for doing these simplifications proliferate within the network literature, researchers would benefit from some guidelines about which of the so-called community detection algorithms are most appropriate for the structures they are studying and the questions they are asking. Here we show that different methods highlight different aspects of a network's structure and that the the sort of information that we seek to extract about the system must guide us in our decision. For example, many community detection algorithms, including the popular modularity maximization approach, infer module assignments from an underlying model of the network formation process. However, we are not always as interested in how a system's network structure was formed, as we are in how a network's extant structure influences the system's behavior. To see how structure influences current behavior, we will recognize that links in a network induce movement across the network and result in system-wide interdependence. In doing so, we explicitly acknowledge that most networks carry flow. To highlight and simplify the network structure with respect to this flow, we use the map equation. We present an intuitive derivation of this flow-based and information-theoretic method and provide an interactive on-line application that anyone can use to explore the mechanics of the map equation. The differences between the map equation and the modularity maximization approach are not merely conceptual. Because the map equation attends to patterns of flow on the network and the modularity maximization approach does not, the two methods can yield dramatically different results for some network structures. To illustrate this and build our understanding of each method, we partition several sample networks. We also describe an algorithm and provide source code to efficiently decompose large weighted and directed networks based on the map equation.
Subfields: Geography, Planning and Development, Statistical and Nonlinear Physics, Signal Processing
View Paper: https://www.semanticscholar.org/paper/b6081f85805499e3259f0fbd13cb7676da15b680
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Geography, Planning and Development
- Tiago P. Peixoto
- Olaf Sporns
- Richard F. Betzel
- Martin Rosvall
- Carl T. Bergstrom
- James A. Evans
- Andrey Rzhetsky
- Kate Starbird
In Statistical and Nonlinear Physics
- Tiago P. Peixoto
- Olaf Sporns
- Richard F. Betzel
- Santo Fortunato
- Andrea Lancichinetti
- Renaud Lambiotte
- Martin Rosvall
- James A. Evans
In Signal Processing
- Tiago P. Peixoto
- Olaf Sporns
- Richard F. Betzel
- Martin Rosvall
- Carl T. Bergstrom
- James A. Evans
- Andrey Rzhetsky
- Kate Starbird
Citations in the corpus
- 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.”
- Modular Brain Networks (2015, positive): “Using these lists along with an indicator that tells when the walker is entering a new community, one can describe the random walk much more efficiently (Rosvall et al. 2009).”
- The Role of Gender in Scholarly Authorship (2012, background): “topology of scientific networks can be used to map the structure of science, and the map equation [13,14] has proven to be a particularly effective method [15].”
- Tradition and Innovation in Scientists’ Research Strategies (2013, methodology): “We apply it to the relevant network for each year and select the best result out of 50 randomly seeded iterations (30, 31).”
- Memory in network flows and its effects on spreading dynamics and community detection (2013, background): “ent. The memory effects on community detection have important network-theoretical implications. Community-detection methods typically identify modules with stronger internal than external connections (26,27) or with relatively long flow persistence times (23,25). A problem with these methods is that ”
- Examining Trolls and Polarization with a Retweet Network (2018, methodology): “the Infomap optimization of the map equation [6, 15] to the graph.”
- Open Community Challenge Reveals Molecular Network Modules with Key Roles in Diseases (2018, methodology): “Several teams used the established Walktrap (Pons and Latapy, 2005) and Infomap (Rosvall et al., 2009) algorithms.”
- Hiding individuals and communities in a social network (2016, methodology): “1), namely: Eigenvector [25], Betweenness [26], Walktrap [29], Louvain [6], Greedy [7], Infomap [31] and Spinglass [30].”
- Mapping Change in Large Networks (2008, background): “ap equation is to nd the structures within a network that are signicant with respect to how information or resources ow through that network. For a detailed description of the map equation, see ref. (3). For a dynamic visualization of the mechanics of the map equation, see http://www.mapequation.org”
- Multilevel Compression of Random Walks on Networks Reveals Hierarchical Organization in Large Integrated Systems (2010, methodology): “This approach uses a random walk as a proxy for the real flow (14, 15), and exploits the duality between compressing a message and finding patterns in the structure that generates that message (16, 17).”