Achieving Optimal Misclassification Proportion in Stochastic Block Models
Abstract
Community detection is a fundamental statistical problem in network data analysis. In this paper, we present a polynomial time two-stage method that provably achieves optimal statistical performance in misclassification proportion for stochastic block model under weak regularity conditions. Our two-stage procedure consists of a refinement stage motivated by penalized local maximum likelihood estimation. This stage can take a wide range of weakly consistent community detection procedures as its initializer, to which it applies and outputs a community assignment that achieves optimal misclassification proportion with high probability. The theoretical property is confirmed by simulated examples.
Cite
Text
Gao et al. "Achieving Optimal Misclassification Proportion in Stochastic Block Models." Journal of Machine Learning Research, 2017.Markdown
[Gao et al. "Achieving Optimal Misclassification Proportion in Stochastic Block Models." Journal of Machine Learning Research, 2017.](https://mlanthology.org/jmlr/2017/gao2017jmlr-achieving/)BibTeX
@article{gao2017jmlr-achieving,
title = {{Achieving Optimal Misclassification Proportion in Stochastic Block Models}},
author = {Gao, Chao and Ma, Zongming and Zhang, Anderson Y. and Zhou, Harrison H.},
journal = {Journal of Machine Learning Research},
year = {2017},
pages = {1-45},
volume = {18},
url = {https://mlanthology.org/jmlr/2017/gao2017jmlr-achieving/}
}