A General Optimization Technique for High Quality Community Detection in Complex Networks

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.

MAIN text: 14 pages, 4 figures, 1 table Supplementary information: 19 pages, 8 figures, 5 tables

References in corpus (20)

• Fast unfolding of communities in large networks
• Modularity and community structure in networks
• Uncovering the overlapping community structure of complex networks in nature and society
• 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
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Comparing community structure identification
• Stochastic blockmodels and community structure in networks
• Finding statistically significant communities in 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
• 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
• Phase transition in the detection of modules in sparse networks
• Delineating geographical regions with networks of human interactions in an extensive set of countries
• Community detection and graph partitioning
• Surprise maximization reveals the community structure of complex 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