Achieving Optimal Misclassification Proportion in Stochastic Block Model
作者： Harrison H. Zhou , Chao Gao , Zongming Ma , Anderson Y. Zhang
DOI:
关键词:
摘要: Community detection is a fundamental statistical problem in network data analysis. Many algorithms have been proposed to tackle this problem. Most of these are not guaranteed achieve the optimality problem, while procedures that information theoretic limits for general parameter spaces computationally tractable. In paper, we present feasible two-stage method achieves optimal performance misclassification proportion stochastic block model under weak regularity conditions. Our procedure consists generic refinement step can take wide range weakly consistent community as initializer, which stage applies and outputs assignment achieving with high probability. The practical effectiveness new algorithm demonstrated by competitive numerical results.
arxiv.org
harvard.edu参考文章(74)
Yogish Sabharwal, Amit Kumar, Sandeep Sen, A simple linear time ( 1+ ε)- approximation algorithm for geometric k-means clustering in any dimensions IEEE. ,(2004)
Y. X. Rachel Wang, Peter J. Bickel, Likelihood-based model selection for stochastic block models arXiv: Statistics Theory. ,(2015)
Van Vu, A simple SVD algorithm for finding hidden partitions arXiv: Combinatorics. ,(2014)
Alexandre B. Tsybakov, Introduction to Nonparametric Estimation ,(2008)
Alexandre Proutière, Se-Young Yun, Accurate Community Detection in the Stochastic Block Model via Spectral Algorithms. arXiv: Social and Information Networks. ,(2014)
Jing Lei, Lingxue Zhu, A Generic Sample Splitting Approach for Refined Community Recovery in Stochastic Block Models arXiv: Machine Learning. ,(2014) , 10.5705/SS.202015.0279
Afonso S. Bandeira, Emmanuel Abbe, Georgina Hall, Exact Recovery in the Stochastic Block Model arXiv: Social and Information Networks. ,(2014)
Purnamrita Sarkar, Peter J. Bickel, Role of Normalization in Spectral Clustering for Stochastic Blockmodels arXiv: Machine Learning. ,(2013) , 10.1214/14-AOS1285
F. McSherry, Spectral partitioning of random graphs international conference on cluster computing. pp. 529- 537 ,(2001) , 10.1109/SFCS.2001.959929
Zhaoran Wang, Huanran Lu, Han Liu, Nonconvex Statistical Optimization: Minimax-Optimal Sparse PCA in Polynomial Time. arXiv: Machine Learning. ,(2014)