Estimating the Number of Communities in a Network

2016/05/31 by M. E. J. Newman, Michael Newman, Gesine Reinert
Computer Science · Mathematics · Physics and Astronomy · #Complex Network Analysis Techniques #Computer science #Opinion Dynamics and Social Influence #Physics #Statistical physics #Stochastic processes and statistical mechanics #cs.SI #physics.soc-ph

paper · pdf · doi:10.1103/physrevlett.117.078301

published as Phys. Rev. Lett. 117, 078301 (2016) · 6 pages, 2 figures. Minor updates and additions in this version

openalex publication_date 2016/08/11 · arxiv created 2016/08/23 · arxiv updated 2016/08/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06

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 effective 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 by maximizing the integrated likelihood of the observed network structure under an appropriate generative model. We demonstrate the approach on a range of benchmark networks, both real and computer generated.

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
• Modularity-maximizing graph communities via mathematical programming
• 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