### 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 connected independently with probability p within clusters and q across clusters. In the asymptotic regime of p = a log n/n and q = b log n/n for fixed a, b and n → ∞, 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. [1]. 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) |
---|---|

Title of host publication | Proceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015 |

Publisher | Institute of Electrical and Electronics Engineers Inc. |

Pages | 1442-1446 |

Number of pages | 5 |

ISBN (Electronic) | 9781467377041 |

DOIs | |

State | Published - Sep 28 2015 |

Event | IEEE International Symposium on Information Theory, ISIT 2015 - Hong Kong, Hong Kong Duration: Jun 14 2015 → Jun 19 2015 |

### Publication series

Name | IEEE International Symposium on Information Theory - Proceedings |
---|---|

Volume | 2015-June |

ISSN (Print) | 2157-8095 |

### Other

Other | IEEE International Symposium on Information Theory, ISIT 2015 |
---|---|

Country | Hong Kong |

City | Hong Kong |

Period | 6/14/15 → 6/19/15 |

### Fingerprint

### ASJC Scopus subject areas

- Theoretical Computer Science
- Information Systems
- Modeling and Simulation
- Applied Mathematics

### Cite this

*Proceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015*(pp. 1442-1446). [7282694] (IEEE International Symposium on Information Theory - Proceedings; Vol. 2015-June). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT.2015.7282694

**Achieving exact cluster recovery threshold via semidefinite programming.** / Hajek, Bruce; Wu, Yihong; Xu, Jiaming.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

*Proceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015.*, 7282694, IEEE International Symposium on Information Theory - Proceedings, vol. 2015-June, Institute of Electrical and Electronics Engineers Inc., pp. 1442-1446, IEEE International Symposium on Information Theory, ISIT 2015, Hong Kong, Hong Kong, 6/14/15. https://doi.org/10.1109/ISIT.2015.7282694

}

TY - GEN

T1 - Achieving exact cluster recovery threshold via semidefinite programming

AU - Hajek, Bruce

AU - Wu, Yihong

AU - Xu, Jiaming

PY - 2015/9/28

Y1 - 2015/9/28

N2 - 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 independently with probability p within clusters and q across clusters. In the asymptotic regime of p = a log n/n and q = b log n/n for fixed a, b and n → ∞, 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. [1]. 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.

AB - 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 independently with probability p within clusters and q across clusters. In the asymptotic regime of p = a log n/n and q = b log n/n for fixed a, b and n → ∞, 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. [1]. 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.

UR - http://www.scopus.com/inward/record.url?scp=84969820675&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84969820675&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2015.7282694

DO - 10.1109/ISIT.2015.7282694

M3 - Conference contribution

AN - SCOPUS:84969820675

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 1442

EP - 1446

BT - Proceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015

PB - Institute of Electrical and Electronics Engineers Inc.

ER -