## 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) |
---|---|

Article number | 7440870 |

Pages (from-to) | 2788-2797 |

Number of pages | 10 |

Journal | IEEE Transactions on Information Theory |

Volume | 62 |

Issue number | 5 |

DOIs | |

State | 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