Source-linked AI summary
Estimating the number of communities in a network
M. E. J. Newman, Gesine Reinert
TL;DR
The paper addresses how to determine a network’s number of communities when existing methods require that number in advance. It uses statistical inference and Monte Carlo sampling to estimate community count, correctly recovering known counts across synthetic and real-world benchmarks.
Problem
Most community-detection methods divide networks into a fixed number of groups, so the appropriate number must be known in advance.
Method
The method fits a stochastic block model using integrated likelihoods, then samples community assignments and community counts with Monte Carlo methods to estimate P(k|A).
Results
The method returns the correct community count on synthetic networks and on four real-world networks with known community structure.
Takeaways & Limitations
A first-principles statistical method can infer the number of network communities while scaling to data sets with hundreds of thousands of nodes or more.
Takeaways & Limitations
The model parameters are not identifiable without imposing a normalization on the node-specific parameters within each group.
Abstract
from arXiv · showhide
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.