Comparative analysis on the selection of number of clusters in community detection

2016/06/30 by Tatsuro Kawamoto, Yoshiyuki Kabashima · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #Algorithm #Artificial intelligence #COVID-19 epidemiological studies #Cluster analysis #Complex Network Analysis Techniques #Computer science #Data mining #Focus (optics) #Inference #Machine learning #Mathematics #Model selection #Modularity (biology) #Opinion Dynamics and Social Influence #Overfitting #Selection (genetic algorithm) #Statistical inference #Statistics #Stochastic block model #cs.SI #physics.soc-ph

paper · pdf · doi:10.1103/physreve.97.022315

published as Phys. Rev. E 97, 022315 (2018) · 21 pages, 14 figures, 2 tables

openalex publication_date 2018/02/28 · arxiv created 2018/03/07 · arxiv updated 2018/03/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

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.

Citations

• Community structure in social and biological networks
• Reconstruction and estimation in the planted partition model
• Community detection in complex networks using extremal optimization
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Spectral redemption in clustering sparse networks
• Performance of modularity maximization in practical contexts
• The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations
• Stochastic blockmodels and community structure in networks
• Community detection in graphs
• A tutorial on spectral clustering
• Maps of random walks on complex networks reveal community structure
• The ground truth about metadata and community detection in networks

Cited by

• Robust Markov stability for community detection at a scale learned based on the structure