Achieving exact cluster recovery threshold via semidefinite programming under the stochastic block model
作者： Yihong Wu , Jiaming Xu , Bruce Hajek
DOI: 10.1109/ACSSC.2015.7421303
关键词: Cluster (physics) 、 Maximum likelihood 、 Stochastic block model 、 Relaxation (approximation) 、 Applied mathematics 、 Conjecture 、 Combinatorics 、 Binary number 、 Semidefinite programming 、 Mathematics
摘要: Resolving a conjecture of Abbe, Bandeira and Hall, the authors have recently shown that semidefinite programming (SDP) relaxation maximum likelihood estimator achieves sharp threshold for exactly recovering community structure under binary stochastic block model two equal-sized clusters. Extending proof techniques, in this paper it is SDP relaxations also achieve recovery with fixed number
sci-hub.se 参考文章(34)
Brendan P. W. Ames, Robust convex relaxation for the planted clique and densest k-subgraph problems arXiv: Optimization and Control. ,(2013)
Alexander S. Wein, Amelia Perry, A semidefinite program for unbalanced multisection in the stochastic block model arXiv: Data Structures and Algorithms. ,(2015)
Alexandre Proutière, Se-Young Yun, Accurate Community Detection in the Stochastic Block Model via Spectral Algorithms. arXiv: Social and Information Networks. ,(2014)
A. Frieze, M. Jerrum, Improved approximation algorithms for MAX k-CUT and MAX BISECTION Algorithmica. ,vol. 18, pp. 67- 81 ,(1997) , 10.1007/BF02523688
F. McSherry, Spectral partitioning of random graphs international conference on cluster computing. pp. 529- 537 ,(2001) , 10.1109/SFCS.2001.959929
Andrea Montanari, Subhabrata Sen, Semidefinite Programs on Sparse Random Graphs. arXiv: Discrete Mathematics. ,(2015)
Emmanuel Abbe, Colin Sandon, Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms arXiv: Probability. ,(2015)
Babak Hassibi, Samet Oymak, Finding Dense Clusters via "Low Rank + Sparse" Decomposition arXiv: Machine Learning. ,(2011)
Elchanan Mossel, Joe Neeman, Allan Sly, A Proof Of The Block Model Threshold Conjecture arXiv: Probability. ,(2013)
Brendan P. W. Ames, Stephen A. Vavasis, Convex optimization for the planted k-disjoint-clique problem Mathematical Programming. ,vol. 143, pp. 299- 337 ,(2014) , 10.1007/S10107-013-0733-1