Provable estimation of the number of blocks in block models

Conference Paper

Community detection is a fundamental unsupervised learning problem for unlabeled networks which has a broad range of applications. Many community detection algorithms assume that the number of clusters r is known apriori. In this paper, we propose an approach based on semi-definite relaxations, which does not require prior knowledge of model parameters like many existing convex relaxation methods and recovers the number of clusters and the clustering matrix exactly under a broad parameter regime, with probability tending to one. On a variety of simulated and real data experiments, we show that the proposed method often outperforms state-of-the-art techniques for estimating the number of clusters.

Duke Authors

Cited Authors

  • Yan, B; Sarkar, P; Cheng, X

Published Date

  • January 1, 2018

Published In

  • International Conference on Artificial Intelligence and Statistics, Aistats 2018

Start / End Page

  • 1185 - 1194

Citation Source

  • Scopus