When are networks truly modular?
arXiv:cond-mat/0606220 · doi:10.1016/j.physd.2006.09.009
Abstract
Study of the cluster- or community structure of complex networks makes an important contribution to the understanding of networks at a functional level. Despite the many efforts, no definition of community has been agreed on and important aspects such as the statistical significance and theoretical limits of community detection are not well understood. We show how the problem of community detection can be mapped onto finding the ground state of an infinite range spin glass. The ground state energy then corresponds directly to the quality of the partition. The network modularity Q previously defined by Girvan and Newman [Phys. Rev. E, 69, 026113 (2004)] turns out to be a special case of this spin glass energy. Through this spin glass analogy, we are able to give expectation values for the modularity of random graphs that can be used in the assessment of the statistical significance of real network clusterings. Further, it allows for assessing the theoretical limits of community detection.
References in corpus (16)
- Statistical mechanics of complex networks
- The structure and function of complex networks
- Community structure in social and biological networks
- Finding and evaluating community structure in networks
- Finding community structure in very large networks
- Fast algorithm for detecting community structure in networks
- Uncovering the overlapping community structure of complex networks in nature and society
- Cooperative Game Theory Approaches for Network Partitioning
- Functional cartography of complex metabolic networks
- Comparing community structure identification
- Defining and identifying communities in networks
- Statistical Mechanics of Community Detection
- Community detection in complex networks using Extremal Optimization
- Modularity from Fluctuations in Random Graphs and Complex Networks
- Detecting fuzzy community structures in complex networks with a Potts model
- Clique percolation in random networks
Cited by in corpus (37)
- Community detection in graphs
- Characterization of complex networks: A survey of measurements
- Community detection algorithms: a comparative analysis
- Finding statistically significant communities in networks
- The performance of modularity maximization in practical contexts
- Overlapping Community Detection in Networks: the State of the Art and Comparative Study
- An information-theoretic framework for resolving community structure in complex networks
- Limits of modularity maximization in community detection
- Robustness of community structure in networks
- Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
- Significant Scales in Community Structure
- Statistical significance of communities in networks
- Nonparametric weighted stochastic block models
- Partitioning and modularity of graphs with arbitrary degree distribution
- Communities and bottlenecks: Trees and treelike networks have high modularity
- Finding and testing network communities by lumped Markov chains
- Local dominance unveils clusters in networks
- Consistency of community structure in complex networks
- Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths
- The role of endogenous and exogenous mechanisms in the formation of R&D networks
- Natural emergence of clusters and bursts in network evolution
- Inversion method for content-based networks
- Fast and accurate determination of modularity and its effect size
- Data-driven modeling of collaboration networks: A cross-domain analysis
- Quality functions in community detection
- Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection
- Statistical Mechanics of Semi-Supervised Clustering in Sparse Graphs
- The Asymptotic Distribution of Modularity in Weighted Signed Networks
- Extending modularity by capturing the similarity attraction feature in the null model
- Detecting Statistically Significant Communities
- A Statistical Density-Based Analysis of Graph Clustering Algorithm Performance
- Metrics for Community Analysis: A Survey
- Block-corrected Modularity for Community Detection
- On Varying Topology of Complex Networks and Performance Limitations of Community Detection Algorithms
- Approximate Conditional Sampling for Pattern Detection in Weighted Networks
- Modularity of Erdős-Rényi random graphs
- Modularity of regular and treelike graphs