Maps of random walks on complex networks reveal community structure

By Martin Rosvall, Carl T. Bergstrom. 2007

4,531 citations recorded by the source corpus.

To comprehend the multipartite organization of large-scale biological and social systems, we introduce an information theoretic approach that reveals community structure in weighted and directed networks. We use the probability flow of random walks on a network as a proxy for information flows in the real system and decompose the network into modules by compressing a description of the probability flow. The result is a map that both simplifies and highlights the regularities in the structure and their relationships. We illustrate the method by making a map of scientific communication as captured in the citation patterns of >6,000 journals. We discover a multicentric organization with fields that vary dramatically in size and degree of integration into the network of science. Along the backbone of the network—including physics, chemistry, molecular biology, and medicine—information flows bidirectionally, but the map reveals a directional pattern of citation from the applied fields to the basic sciences.

Subfields: Molecular Biology, Statistical and Nonlinear Physics

How researchers see this paper

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

In Molecular Biology

In Statistical and Nonlinear Physics

Citations in the corpus

Community detection in graphs (2009, methodology): “Rosvall and Bergstrom raised similar objections (Rosvall and Bergstrom, 2008).”
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.”
Detecting the dynamics of urban structure through spatial network analysis (2014, methodology): “According to the comparative analysis of different methods (Lancichinetti and Fortunato 2009), the map equation approach called Infomap developed by (Rosvall and Bergstrom 2008) is one of the recent algorithms that has shown excellent performance in generating such a two-level hierarchy of clusters ”
Novel R tools for analysis of genome-wide population genetic data with emphasis on clonality (2015, methodology): “To detect mlg clusters, the infoMAP community detection algorithm was applied with 10,000 trials as implemented in the R package igraph version 0.7.1 utilizing genetic distance as edge weights and number of samples in each MLG as vertex weights (Csardi and Nepusz, 2006; Rosvall and Bergstrom, 2008).”
Communities in Networks (2009, background): “Even more exciting, one can relate resolution parameters to the time scales of dynamical processes unfolding on a network [27,68,98,108].”
Overlapping community detection in networks: The state-of-the-art and comparative study (2011, methodology): “Kim [Kim and Jeong 2011] extended the map equation method (also known as Infomap [M. Rosvall 2008]) to the line graph, which encodes the path of the random walk on the line network under the Minimum Description Length (MDL) principle.”
Cellular and inter-cellular rewiring of the human colon during ulcerative colitis (2019, methodology): “The Infomap graph clustering algorithm (Rosvall and Bergstrom, 2008) was then applied to the k-nearest neighbor (k-NN) graph defined using PCs 1 to 20 and k = 50 nearest neighbors.”
Complex Network Clustering by Multiobjective Discrete Particle Swarm Optimization Based on Decomposition (2014, methodology): “Informap was proposed by Rosvall and Bergstrom [61].”
Measuring Scholarly Impact (2014, methodology): “For instance, Infomap not only provides two-level, multi-level, and overlapping solutions for analyzing undirected, directed, unweighted, and weighted networks, but also for analyzing networks that contain higher-order data, such as memory networks (Rosvall, Esquivel, West, Lancichinetti, & Lambiott”
Community-Affiliation Graph Model for Overlapping Network Community Detection (2012, methodology): “Experiments on social, collaboration, information and biological networks reveal that AGM discovers overlapping as well as non-overlapping community structure more accurately than present state-of-the-art methods [1], [23], [2], [26].”
Memory in network flows and its effects on spreading dynamics and community detection (2013, methodology): “een) or all other journals (yellow), (2) internal ﬂow coming from journals without crossing community boundaries (dark blue) versus external ﬂow that does cross community boundaries (light blue), and (3) return ﬂow after two steps on the network (dark red) versus lost ﬂow after two steps on the netw”
A Cancer Cell Program Promotes T Cell Exclusion and Resistance to Checkpoint Blockade (2018, positive): “Next, we clustered the cells with the Infomap algorithm (Rosvall and Bergstrom, 2008).”