Achieving Optimal Misclassification Proportion in Stochastic Block Models

Chao Gao, Zongming Ma, Anderson Y. Zhang, Harrison H. Zhou; 18(60):1−45, 2017.

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.

[abs][pdf][bib]