A General Optimization Technique for High Quality Community Detection in Complex Networks
arXiv:1308.3508 · doi:10.1103/PhysRevE.90.012811
Abstract
Recent years have witnessed the development of a large body of algorithms for community detection in complex networks. Most of them are based upon the optimization of objective functions, among which modularity is the most common, though a number of alternatives have been suggested in the scientific literature. We present here an effective general search strategy for the optimization of various objective functions for community detection purposes. When applied to modularity, on both real-world and synthetic networks, our search strategy substantially outperforms the best existing algorithms in terms of final scores of the objective function; for description length, its performance is on par with the original Infomap algorithm. The execution time of our algorithm is on par with non-greedy alternatives present in literature, and networks of up to 10,000 nodes can be analyzed in time spans ranging from minutes to a few hours on average workstations, making our approach readily applicable to tasks which require the quality of partitioning to be as high as possible, and are not limited by strict time constraints. Finally, based on the most effective of the available optimization techniques, we compare the performance of modularity and code length as objective functions, in terms of the quality of the partitions one can achieve by optimizing them. To this end, we evaluated the ability of each objective function to reconstruct the underlying structure of a large set of synthetic and real-world networks.
arXiv commentMAIN text: 14 pages, 4 figures, 1 table Supplementary information: 19 pages, 8 figures, 5 tables
References in corpus (41)
- Fast unfolding of communities in large networks
- Community structure in social and biological networks
- Finding and evaluating community structure in networks
- Modularity and community structure in networks
- Community detection in graphs
- 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
- Lethality and centrality in protein networks
- Finding community structure in networks using the eigenvectors of matrices
- Cooperative Game Theory Approaches for Network Partitioning
- Maps of random walks on complex networks reveal community structure
- The architecture of complex weighted networks
- Functional cartography of complex metabolic networks
- Benchmark graphs for testing community detection algorithms
- Resolution limit in community detection
- Comparing community structure identification
- Community detection algorithms: a comparative analysis
- Stochastic blockmodels and community structure in networks
- Community detection in complex networks using Extremal Optimization
- Finding statistically significant communities in networks
- Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
- The performance of modularity maximization in practical contexts
- Modularity from Fluctuations in Random Graphs and Complex Networks
- An information-theoretic framework for resolving community structure in complex networks
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- Hierarchical modularity in human brain functional networks
- Geo-located Twitter as the proxy for global mobility patterns
- Analysis of the structure of complex networks at different resolution levels
- Fuzzy communities and the concept of bridgeness in complex networks
- Phase transition in the detection of modules in sparse networks
- An efficient and principled method for detecting communities in networks
- Multiresolution community detection for megascale networks by information-based replica correlations
- The structure of borders in a small world
- Delineating geographical regions with networks of human interactions in an extensive set of countries
- Improved community structure detection using a modified fine tuning strategy
- Community detection and graph partitioning
- Deciphering Network Community Structure by Surprise
- Model Selection for Degree-corrected Block Models
- Surprise maximization reveals the community structure of complex networks
- Significant communities in large sparse networks
Cited by in corpus (21)
- Geo-located Twitter as the proxy for global mobility patterns
- A Comprehensive Survey on Community Detection with Deep Learning
- Nestedness in complex networks: Observation, emergence, and implications
- Delineating geographical regions with networks of human interactions in an extensive set of countries
- IEDC: An Integrated Approach for Overlapping and Non-overlapping Community Detection
- Identifying the structural discontinuities of human interactions
- Revealing In-Block Nestedness: detection and benchmarking
- Fast and accurate determination of modularity and its effect size
- Detection of Community Structures in Networks with Nodal Features based on Generative Probabilistic Approach
- Randomizing growing networks with a time-respecting null model
- Information theoretic network approach to socioeconomic correlations
- Heuristic Modularity Maximization Algorithms for Community Detection Rarely Return an Optimal Partition or Anything Similar
- Entropy-based randomisation of rating networks
- Bayan Algorithm: Detecting Communities in Networks Through Exact and Approximate Optimization of Modularity
- The Impact of Social Segregation on Human Mobility in Developing and Urbanized Regions
- Pattern and Anomaly Detection in Urban Temporal Networks
- Subnetwork Constraints for Tighter Upper Bounds and Exact Solution of the Clique Partitioning Problem
- Absence of a resolution limit in in-block nestedness
- Learning dynamic representations of the functional connectome in neurobiological networks
- Transfer Learning from an Auxiliary Discriminative Task for Unsupervised Anomaly Detection
- Tweeting Over The Border: An Empirical Study of Transnational Migration in San Diego and Tijuana