Resolution limit in community detection
arXiv:physics/0607100 · doi:10.1073/pnas.0605965104
Abstract
Detecting community structure is fundamental to clarify the link between structure and function in complex networks and is used for practical applications in many disciplines. A successful method relies on the optimization of a quantity called modularity [Newman and Girvan, Phys. Rev. E 69, 026113 (2004)], which is a quality index of a partition of a network into communities. We find that modularity optimization may fail to identify modules smaller than a scale which depends on the total number L of links of the network and on the degree of interconnectedness of the modules, even in cases where modules are unambiguously defined. The probability that a module conceals well-defined substructures is the highest if the number of links internal to the module is of the order of \sqrt{2L} or smaller. We discuss the practical consequences of this result by analyzing partitions obtained through modularity optimization in artificial and real networks.
8 pages, 3 figures. Clarification of definition of community in Section II + minor revisions
References in corpus (2)
Cited by in corpus (50)
- Fast unfolding of communities in large networks
- Benchmark graphs for testing community detection algorithms
- Detecting the overlapping and hierarchical community structure of complex networks
- Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
- An information-theoretic framework for resolving community structure in complex networks
- Modularity and community detection in bipartite networks
- Communicability in complex networks
- Detect overlapping and hierarchical community structure in networks
- Extracting the hierarchical organization of complex systems
- Community detection in networks with positive and negative links
- Analysis of the structure of complex networks at different resolution levels
- Detecting network communities by propagating labels under constraints
- Robustness of community structure in networks
- Extending the definition of modularity to directed graphs with overlapping communities
- Modularity-Maximizing Network Communities via Mathematical Programming
- A Bayesian Approach to Network Modularity
- Towards real-time community detection in large networks
- Analysis of community structure in networks of correlated data
- Modularity clustering is force-directed layout
- Emergence of communities in weighted networks
- Evaluating Local Community Methods in Networks
- Limited resolution in complex network community detection with Potts model approach
- Identifying network communities with a high resolution
- Maximizing Modularity is hard
- Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement
- Community Structure in Congressional Cosponsorship Networks
- Topology and Evolution of Technology Innovation Networks
- Quantifying and identifying the overlapping community structure in networks
- Motif-based communities in complex networks
- Spectral tripartitioning of networks
- A New Comparative Definition of Community and Corresponding Identifying Algorithm
- Impact of community structure on information transfer
- Multistep greedy algorithm identifies community structure in real-world and computer-generated networks
- Detection of node group membership in networks with group overlap
- Deterministic Modularity Optimization
- Community Detection in Complex Networks by Dynamical Simplex Evolution
- Inversion method for content-based networks
- Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters
- Detecting modules in dense weighted networks with the Potts method
- Overlapping Community Detection in Bipartite Networks
- Component models for large networks
- Spectral methods and cluster structure in correlation-based networks
- Finding Community Structure Based on Subgraph Similarity
- Partition of Networks into Basins of Attraction
- Quality functions in community detection
- Detecting groups of similar components in complex networks
- Consistent Community Identification in Complex Networks
- Enhance the Efficiency of Heuristic Algorithm for Maximizing Modularity Q
- Communities recognition in the Chesapeake Bay ecosystem by dynamical clustering algorithms based on different oscillators systems
- Can extremism guarantee pluralism?