Provable Estimation of the Number of Blocks in Block Models
Abstract
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.
Cite
Text
Yan et al. "Provable Estimation of the Number of Blocks in Block Models." International Conference on Artificial Intelligence and Statistics, 2018.Markdown
[Yan et al. "Provable Estimation of the Number of Blocks in Block Models." International Conference on Artificial Intelligence and Statistics, 2018.](https://mlanthology.org/aistats/2018/yan2018aistats-provable/)BibTeX
@inproceedings{yan2018aistats-provable,
title = {{Provable Estimation of the Number of Blocks in Block Models}},
author = {Yan, Bowei and Sarkar, Purnamrita and Cheng, Xiuyuan},
booktitle = {International Conference on Artificial Intelligence and Statistics},
year = {2018},
pages = {1185-1194},
url = {https://mlanthology.org/aistats/2018/yan2018aistats-provable/}
}