# Probabilistic community detection with unknown number of communities

arXiv: https://arxiv.org/abs/1602.08062 · HTML: https://mlsanity.com/paper/1602.08062/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Feb 2016.

## Built on by (most cited first, 5 of 5)

- [Adaptive variational Bayes: Optimality, computation and applications](https://mlsanity.com/paper/2109.03204/) (2021)
- [Community Detection in General Hypergraph via Graph Embedding](https://mlsanity.com/paper/2103.15035/) (2021)
- [Why the Rich Get Richer? On the Balancedness of Random Partition Models](https://mlsanity.com/paper/2201.12697/) (2022)
- [Bayesian nonparametric mixture inconsistency for the number of components: How worried should we be in practice?](https://mlsanity.com/paper/2207.14717/) (2022)
- [Modeling Random Networks with Heterogeneous Reciprocity](https://mlsanity.com/paper/2308.10113/) (2023)

## Abstract (arXiv)

A fundamental problem in network analysis is clustering the nodes into groups which share a similar connectivity pattern. Existing algorithms for community detection assume the knowledge of the number of clusters or estimate it a priori using various selection criteria and subsequently estimate the community structure. Ignoring the uncertainty in the first stage may lead to erroneous clustering, particularly when the community structure is vague. We instead propose a coherent probabilistic framework for simultaneous estimation of the number of communities and the community structure, adapting recently developed Bayesian nonparametric techniques to network models. An efficient Markov chain Monte Carlo (MCMC) algorithm is proposed which obviates the need to perform reversible jump MCMC on the number of clusters. The methodology is shown to outperform recently developed community detection algorithms in a variety of synthetic data examples and in benchmark real-datasets. Using an appropriate metric on the space of all configurations, we develop non-asymptotic Bayes risk bounds even when the number of clusters is unknown. Enroute, we develop concentration properties of non-linear functions of Bernoulli random variables, which may be of independent interest.