Probabilistic Community Detection With Unknown Number of Communities
Authors:
- 11 July 2018
- journal article
- research article
- Published by Taylor & Francis in Journal of the American Statistical Association
- Vol. 114 (526) , 893-905
Abstract
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 nonasymptotic Bayes risk bounds even when the number of clusters is unknown. Enroute, we develop concentration properties of nonlinear functions of Bernoulli random variables, which may be of independent interest in analysis of related models. Supplementary materials for this article are available online.Keywords
All Related Versions
This publication has 44 references indexed in Scilit:
- Consistency of community detection in networks under degree-corrected stochastic block modelsThe Annals of Statistics, 2012
- Variational Bayesian inference and complexity control for stochastic block modelsStatistical Modelling, 2012
- Community extraction for social networksProceedings of the National Academy of Sciences, 2011
- A nonparametric view of network models and Newman–Girvan and other modularitiesProceedings of the National Academy of Sciences, 2009
- Fast online graph clustering via Erdős–Rényi mixturePattern Recognition, 2008
- Markov Chain Sampling Methods for Dirichlet Process Mixture ModelsJournal of Computational and Graphical Statistics, 2000
- Normalized cuts and image segmentationIEEE Transactions on Pattern Analysis and Machine Intelligence, 2000
- Reversible jump Markov chain Monte Carlo computation and Bayesian model determinationBiometrika, 1995
- Exchangeable and partially exchangeable random partitionsProbability Theory and Related Fields, 1995
- Objective Criteria for the Evaluation of Clustering MethodsJournal of the American Statistical Association, 1971