Provable Estimation of the Number of Blocks in Block Models
share
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 relaxation, which recovers the number of clusters and the clustering matrix exactly under a broad parameter regime, with probability tending to one. Compared to existing convex relaxations, our relaxation leads to exact recovery under weaker conditions on cluster separation or cluster sizes. 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.
READ FULL TEXT