# Achieving exact cluster recovery threshold via semidefinite programming

Bruce Hajek, Yihong Wu, Jiaming Xu

Research output: Contribution to journalArticlepeer-review

## Abstract

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 independently connected with probability p within clusters and q across clusters. In the asymptotic regime of nand q=b \log n/n for fixed a,b , and n \to \infty , we show that the semidefinite programming relaxation of the maximum likelihood estimator achieves the optimal threshold for exactly recovering the partition from the graph with probability tending to one, resolving a conjecture of Abbe et al. Furthermore, we show that the semidefinite programming relaxation also achieves the optimal recovery threshold in the planted dense subgraph model containing a single cluster of size proportional to $n$.

Original language English (US) 7440870 2788-2797 10 IEEE Transactions on Information Theory 62 5 https://doi.org/10.1109/TIT.2016.2546280 Published - May 2016

## Keywords

• Community detection
• Erdos-Renyi random graph
• Semidefinite programming
• Stochastic block model

## ASJC Scopus subject areas

• Information Systems
• Computer Science Applications
• Library and Information Sciences

## Fingerprint

Dive into the research topics of 'Achieving exact cluster recovery threshold via semidefinite programming'. Together they form a unique fingerprint.