Achieving Optimal Misclassification Proportion in Stochastic Block Models

作者：Gao Chao; Ma Zongming; Zhang Anderson Y; Zhou Harrison H

来源：Journal of Machine Learning Research, 2017, 18: 1-45.

• Clustering
• Community detection
• Minimax rates
• Network analysis
• Spectral clustering

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.

• 出版日期2017