An information-theoretic framework for resolving community structure in complex networks

By Martin Rosvall, Carl T. Bergstrom. Proceedings of the National Academy of Sciences of the United States of America, 2006

775 citations recorded by the source corpus.

To understand the structure of a large-scale biological, social, or technological network, it can be helpful to decompose the network into smaller subunits or modules. In this article, we develop an information-theoretic foundation for the concept of modularity in networks. We identify the modules of which the network is composed by finding an optimal compression of its topology, capitalizing on regularities in its structure. We explain the advantages of this approach and illustrate them by partitioning a number of real-world and model networks.

Subfields: Molecular Biology, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/a0efc76c89419d65e0d439cf96990c2b99c148aa

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

A nonparametric view of network models and Newman–Girvan and other modularities (2009, methodology): “by Rosvall and Bergstrom using a data compression criterion (21), which is closely related to L-M.”
Mathematical Formulation of Multilayer Networks (2013, background): “For multiplex networks, for example, the most sensible normalization constant is typically the number of layers L.”
Detecting cohesive and 2-mode communities indirected and undirected networks (2014, background): “For example, separate me thods have been proposed for detecting communities in undirected networks that are disjoint [4, 13, 21, 38, 40], overlapping [3, 6 , 11, 34, 43], or hierarchically nested [2, 44].”
Statistical properties of community structure in large social and information networks (2008, background): “In part as a response to this, some recent work has had a more statistical flavor [85, 137, 141, 93, 130].”
Hierarchical block structures and high-resolution model selection in large networks (2013, background): “[32, 37], which considered all possible B B l − 1 l partitions to be equally likely, and, hence, computed the necessary amount of information as B l 1 ln B l .”
The structure and dynamics of multilayer networks (2014, background): “Both the network ensembles and their entropy can be used on several inference problems to extract information from a given network [147,148].”
Community detection in graphs (2009, methodology): “Rosvall and Bergstrom raised similar objections (Rosvall and Bergstrom, 2008).”
Clustering and Community Detection in Directed Networks: A Survey (2013, methodology): “es in networks represent structural patterns and regularities, that similar to more traditional data mining and analysis tasks, they can be used to eectively compress the network (data), e.g., Refs. [91,92]. Rosvall and Bergstrom [18] proposed a method (called Isomap) to identify communities in dire”
The emergence of unshared consensus decisions in bottlenose dolphins (2009, result): “1) in agreement with previous analyses (Newman 2004; Rosvall and Bergstrom 2007; Monni and Li 2008) and observed behavioral variations in the population (Lusseau 2007b; Lusseau et al.”
The Human Thalamus Is an Integrative Hub for Functional Brain Networks (2016, methodology): “First, we identified functional networks using the InfoMap algorithm (Rosvall and Bergstrom, 2007) at a threshold of density =0.15.”
A Comparative Analysis of Community Detection Algorithms on Artificial Networks (2016, methodology): “Infomap This algorithm was proposed by Rosvall et al. 35,36 .”
Network neuroscience (2017, methodology): “This includes characterizing fluctuations in community structure of networks across time 59 , and implementing dynamic processes on networks as a diagnostic tool for explicitly linking micro-scale features of network organization to macro-scale characteristics of neurophysiological dynamics 60 .”
Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters (2008, background): “In part as a response to this, some recent work has had a more statistical flavor [86, 140, 144, 94, 133].”
Global organization of a binding site network gives insight into evolution and structure-function relationships of proteins (2017, methodology): “A community detection analysis was performed using the Infomap method based on the minimum description length principle 36, 37 .”
Morphological Integration and Developmental Modularity (2008, methodology): “In some contexts, information about the network of interactions is readily available, and analyses of modularity can directly use the connections between parts to identify modules (e.g., Girvan & Newman 2002, Guimerà & Nunes Amaral 2005, Rosvall & Bergstrom 2007).”