Achieving Optimal Misclassification Proportion in Stochastic Block Models

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 ] &copy JMLR 2017. ( edit, beta )

Authors

• Chao Gao Northwestern Polytechnical University
• Zongming Ma
• Anderson Y. Zhang University of Pennsylvania
• Harrison H. Zhou

Keywords

No keywords are indexed for this paper.