Comparative analysis on the selection of number of clusters in community detection
arXiv:1606.07668 · doi:10.1103/PhysRevE.97.022315
Abstract
We conduct a comparative analysis on various estimates of the number of clusters in community detection. An exhaustive comparison requires testing of all possible combinations of frameworks, algorithms, and assessment criteria. In this paper we focus on the framework based on a stochastic block model, and investigate the performance of greedy algorithms, statistical inference, and spectral methods. For the assessment criteria, we consider modularity, map equation, Bethe free energy, prediction errors, and isolated eigenvalues. From the analysis, the tendency of overfit and underfit that the assessment criteria and algorithms have, becomes apparent. In addition, we propose that the alluvial diagram is a suitable tool to visualize statistical inference results and can be useful to determine the number of clusters.
arXiv comment21 pages, 14 figures, 2 tables
References in corpus (37)
- 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
- 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
- Resolution limit in community detection
- Community detection algorithms: a comparative analysis
- Statistical Mechanics of Community Detection
- Stochastic blockmodels and community structure in networks
- Community detection in complex networks using Extremal Optimization
- The performance of modularity maximization in practical contexts
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- Spectral redemption: clustering sparse networks
- Mapping change in large networks
- The ground truth about metadata and community detection in networks
- Spectral methods for network community detection and graph partitioning
- Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems
- Phase transition in the detection of modules in sparse networks
- Graph spectra and the detectability of community structure in networks
- Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models
- Identification of core-periphery structure in networks
- Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
- Estimating the number of communities in a network
- Distinct types of eigenvector localization in networks
- Spectra of random graphs with arbitrary expected degrees
- Estimating the resolution limit of the map equation in community detection
- Spectra of random graphs with community structure and arbitrary degrees
- Cross-validation estimate of the number of clusters in a network
- Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors
- Improving the performance of algorithms to find communities in networks
- Spectral density of the non-backtracking operator
- Multiple phases in modularity-based community detection
- Detectability of the spectral method for sparse graph partitioning
Cited by in corpus (8)
- Evaluating Overfit and Underfit in Models of Network Community Structure
- Universality of the stochastic block model
- Counting the number of metastable states in the modularity landscape: Algorithmic detectability limit of greedy algorithms in community detection
- Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection
- Bayan Algorithm: Detecting Communities in Networks Through Exact and Approximate Optimization of Modularity
- Democratic summary of public opinions in free-response surveys
- Single-trajectory map equation
- Identifying macroscopic features in foreign visitor travel pathways