An Information-Theoretic Approach to Network Modularity

Abstract

Exploiting recent developments in information theory, we propose, illustrate, and validate a principled information-theoretic algorithm for module discovery and resulting measure of network modularity. This measure is an order parameter (a dimensionless number between 0 and 1). Comparison is made to other approaches to module-discovery and to quantifying network modularity using Monte Carlo generated Erdos-like modular networks. Finally, the Network Information Bottleneck (NIB) algorithm is applied to a number of real world networks, including the "social" network of coauthors at the APS March Meeting 2004.

13 pages, 8 figures

References in corpus (1)

• Systematic identification of statistically significant network measures

Cited by in corpus (25)

• Community detection in graphs
• Maps of random walks on complex networks reveal community structure
• Characterization of complex networks: A survey of measurements
• The performance of modularity maximization in practical contexts
• The map equation
• An information-theoretic framework for resolving community structure in complex networks
• Extracting the hierarchical organization of complex systems
• Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
• A Bayesian Approach to Network Modularity
• A Classification for Community Discovery Methods in Complex Networks
• Evolution of complex modular biological networks
• Maximizing Modularity is hard
• Think Locally, Act Locally: The Detection of Small, Medium-Sized, and Large Communities in Large Networks
• Improved community structure detection using a modified fine tuning strategy
• Encoding dynamics for multiscale community detection: Markov time sweeping for the Map equation
• Model validation of simple-graph representations of metabolism
• Entropic one-class classifiers
• Network motifs come in sets: correlations in the randomization process
• Graph animals, subgraph sampling and motif search in large networks
• An Information-Theoretic Formalism for Multiscale Structure in Complex Systems
• Graph Theory and Networks in Biology
• A statistical method for revealing form-function relations in biological networks
• Cell biology: Networks, regulation, pathways
• One-class classifiers based on entropic spanning graphs
• Monochromaticity in Neutral Evolutionary Network Models