Community structure: A comparative evaluation of community detection methods
arXiv:1812.06598 · doi:10.1017/nws.2019.59
Abstract
Discovering community structure in complex networks is a mature field since a tremendous number of community detection methods have been introduced in the literature. Nevertheless, it is still very challenging for practioners to determine which method would be suitable to get insights into the structural information of the networks they study. Many recent efforts have been devoted to investigating various quality scores of the community structure, but the problem of distinguishing between different types of communities is still open. In this paper, we propose a comparative, extensive and empirical study to investigate what types of communities many state-of-the-art and well-known community detection methods are producing. Specifically, we provide comprehensive analyses on computation time, community size distribution, a comparative evaluation of methods according to their optimisation schemes as well as a comparison of their partioning strategy through validation metrics. We process our analyses on a very large corpus of hundreds of networks from five different network categories and propose ways to classify community detection methods, helping a potential user to navigate the complex landscape of community detection.
arXiv commentThis version will be published the Network Science journal (http://journals.cambridge.org/NWS)
References in corpus (32)
- Fast unfolding of communities in large networks
- Community structure in social and biological networks
- Modularity and community structure in networks
- Community detection in graphs
- Finding community structure in very large networks
- Natural Scales in Geographical Patterns
- Finding community structure in networks using the eigenvectors of matrices
- Near linear time algorithm to detect community structures in large-scale networks
- Resolution limit in community detection
- Comparing community structure identification
- Defining and identifying communities in networks
- Statistical Mechanics of Community Detection
- Community detection in networks: A user guide
- Finding statistically significant communities in networks
- The map equation
- An information-theoretic framework for resolving community structure in complex networks
- The ground truth about metadata and community detection in networks
- Narrow scope for resolution-limit-free community detection
- A Classification for Community Discovery Methods in Complex Networks
- Characterizing the community structure of complex networks
- Community detection in networks: Structural communities versus ground truth
- Evaluating Overfit and Underfit in Models of Network Community Structure
- The many facets of community detection in complex networks
- Mixing local and global information for community detection in large networks
- Comparative Evaluation of Community Detection Algorithms: A Topological Approach
- Deciphering Network Community Structure by Surprise
- Detecting communities using asymptotical Surprise
- Z-score-based modularity for community detection in networks
- Efficient method for estimating the number of communities in a network
- Guaranteed clustering and biclustering via semidefinite programming
- Post-Processing Hierarchical Community Structures: Quality Improvements and Multi-scale View
- An empirical characterization of community structures in complex networks using a bivariate map of quality metrics