Estimating the number of communities in a network

Abstract

Community detection, the division of a network into dense subnetworks with only sparse connections between them, has been a topic of vigorous study in recent years. However, while there exist a range of powerful and flexible methods for dividing a network into a specified number of communities, it is an open question how to determine exactly how many communities one should use. Here we describe a mathematically principled approach for finding the number of communities in a network using a maximum-likelihood method. We demonstrate the approach on a range of real-world examples with known community structure, finding that it is able to determine the number of communities correctly in every case.

6 pages, 2 figures. Minor updates and additions in this version

References in corpus (10)

• Fast unfolding of communities in large networks
• Cooperative Game Theory Approaches for Network Partitioning
• Resolution limit in community detection
• Stochastic blockmodels and community structure in networks
• An information-theoretic framework for resolving community structure in complex networks
• Missing and spurious interactions and the reconstruction of complex networks
• Phase transition in the detection of modules in sparse networks
• Modularity-Maximizing Network Communities via Mathematical Programming
• A Classification for Community Discovery Methods in Complex Networks
• Model selection and hypothesis testing for large-scale network models with overlapping groups

Cited by in corpus (36)

• Community detection in networks: A user guide
• Social physics
• Community detection in networks: Modularity optimization and maximum likelihood are equivalent
• A Review of Stochastic Block Models and Extensions for Graph Clustering
• Nonparametric Bayesian inference of the microcanonical stochastic block model
• On community structure in complex networks: challenges and opportunities
• Evaluating Overfit and Underfit in Models of Network Community Structure
• Bayesian stochastic blockmodeling
• Element-centric clustering comparison unifies overlaps and hierarchy
• Nonparametric weighted stochastic block models
• Efficient method for estimating the number of communities in a network
• A statistical inference approach to structural reconstruction of complex networks from binary time series
• Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths
• Expectation-Maximizing Network Reconstruction and MostApplicable Network Types Based on Binary Time Series Data
• Merge-split Markov chain Monte Carlo for community detection
• Cross-validation estimate of the number of clusters in a network
• Multiplex decomposition of non-Markovian dynamics and the hidden layer reconstruction problem
• Mean-field theory of graph neural networks in graph partitioning
• Adapting Stochastic Block Models to Power-Law Degree Distributions
• Algorithmic detectability threshold of the stochastic block model
• Optimal community structure for social contagions
• Hierarchical clustering with discrete latent variable models and the integrated classification likelihood
• Hierarchical core-periphery structure in networks
• Comparative analysis on the selection of number of clusters in community detection
• Bayesian estimation of the latent dimension and communities in stochastic blockmodels
• Phase Transitions and a Model Order Selection Criterion for Spectral Graph Clustering
• Counting the number of metastable states in the modularity landscape: Algorithmic detectability limit of greedy algorithms in community detection
• Analytical Formulation of the Block-Constrained Configuration Model
• Finite size analysis of the detectability limit of the stochastic block model
• Estimating the number of communities in weighted networks
• Stochastic Block Models are a Discrete Surface Tension
• Understanding complexity via network theory: a gentle introduction
• Directed degree corrected mixed membership model and estimating community memberships in directed networks
• Monte Carlo goodness-of-fit tests for degree corrected and related stochastic blockmodels
• Finding community structure using the ordered random graph model
• From centre to centres: polycentric structures in individual mobility