Achieving Exact Cluster Recovery Threshold via Semidefinite Programming

Bruce Hajek, Yihong Wu, Jiaming Xu

The binary symmetric stochastic block model deals with a random graph of $n$ vertices partitioned into two equal-sized clusters, such that each pair of vertices is connected indepe…