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

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.

21 pages, 14 figures, 2 tables

References in corpus (19)

• Fast unfolding of communities in large networks
• Modularity and community structure in 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
• Statistical Mechanics of Community Detection
• Stochastic blockmodels and community structure in networks
• The ground truth about metadata and community detection in networks
• 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
• 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
• Spectra of random graphs with arbitrary expected 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
• Spectral density of the non-backtracking operator

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