Efficient method for estimating the number of communities in a network

Abstract

While there exist a wide range of effective methods for community detection in networks, most of them require one to know in advance how many communities one is looking for. Here we present a method for estimating the number of communities in a network using a combination of Bayesian inference with a novel prior and an efficient Monte Carlo sampling scheme. We test the method extensively on both real and computer-generated networks, showing that it performs accurately and consistently, even in cases where groups are widely varying in size or structure.

arXiv comment13 pages, 4 figures

References in corpus (13)

• Community structure in social and biological networks
• Community detection in graphs
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• Benchmark graphs for testing community detection algorithms
• Community detection algorithms: a comparative analysis
• Stochastic blockmodels and community structure in networks
• Community detection in networks: A user guide
• Missing and spurious interactions and the reconstruction of complex networks
• Phase transition in the detection of modules in sparse networks
• Hierarchical Block Structures and High-resolution Model Selection in Large Networks
• Nonparametric Bayesian inference of the microcanonical stochastic block model
• Estimating the number of communities in a network

Cited by in corpus (18)

• On community structure in complex networks: challenges and opportunities
• Bayesian stochastic blockmodeling
• Consistency of community structure in complex networks
• Community structure: A comparative evaluation of community detection methods
• Merge-split Markov chain Monte Carlo for community detection
• Community Detection in Bipartite Networks with Stochastic Blockmodels
• Revealing consensus and dissensus between network partitions
• Hierarchical core-periphery structure in networks
• Hierarchical clustering with discrete latent variable models and the integrated classification likelihood
• Voter model on networks partitioned into two cliques of arbitrary sizes
• Estimating the number of communities in weighted networks
• Stochastic Block Models are a Discrete Surface Tension
• Importance of initial conditions in the polarization of complex networks
• Adjusted chi-square test for degree-corrected block models
• Provable Estimation of the Number of Blocks in Block Models
• Mixture Models and Networks -- Overview of Stochastic Blockmodelling
• Drug-disease networks and drug repurposing
• Reduce the rank calculation of a high-dimensional sparse matrix based on network controllability theory