Efficient method for estimating the number of communities in a network

2017/06/07 by Maria A. Riolo, George T. Cantwell, Gesine Reinert +1 · 1 citation
Computer Science · Engineering · Mathematics · Physics and Astronomy · Social Sciences · #Artificial intelligence #Bayesian network #Community structure #Complex Network Analysis Techniques #Computer science #Data mining #Engineering #Human Mobility and Location-Based Analysis #Inference #Machine learning #Mathematics #Monte Carlo method #Opinion Dynamics and Social Influence #Range (aeronautics) #Sampling (signal processing) #Statistics #cs.SI #physics.soc-ph

paper · pdf · doi:10.1103/physreve.96.032310

published as Phys. Rev. E 96, 032310 (2017) · 13 pages, 4 figures

arxiv created 2017/06/07 · openalex publication_date 2017/09/14 · arxiv updated 2017/09/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06

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.

Citations

• Community structure in social and biological networks
• Reconstruction and estimation in the planted partition model
• Missing and spurious interactions and the reconstruction of complex networks
• Stochastic blockmodels and community structure in networks
• Community detection in graphs

Cited by

• Stochastic Block Models are a Discrete Surface Tension