  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.
