Achieving exact cluster recovery threshold via semidefinite programming under the stochastic block model

Yihong Wu, Jiaming Xu, Bruce Hajek

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Resolving a conjecture of Abbe, Bandeira and Hall, the authors have recently shown that the semidefinite programming (SDP) relaxation of the maximum likelihood estimator achieves the sharp threshold for exactly recovering the community structure under the binary stochastic block model of two equal-sized clusters. Extending the proof techniques, in this paper it is shown that SDP relaxations also achieve the sharp recovery threshold under the stochastic block model with a fixed number of equal-sized clusters.

Original languageEnglish (US)
Title of host publicationConference Record of the 49th Asilomar Conference on Signals, Systems and Computers, ACSSC 2015
EditorsMichael B. Matthews
PublisherIEEE Computer Society
Pages1070-1074
Number of pages5
ISBN (Electronic)9781467385763
DOIs
StatePublished - Feb 26 2016
Event49th Asilomar Conference on Signals, Systems and Computers, ACSSC 2015 - Pacific Grove, United States
Duration: Nov 8 2015Nov 11 2015

Publication series

NameConference Record - Asilomar Conference on Signals, Systems and Computers
Volume2016-February
ISSN (Print)1058-6393

Other

Other49th Asilomar Conference on Signals, Systems and Computers, ACSSC 2015
CountryUnited States
CityPacific Grove
Period11/8/1511/11/15

ASJC Scopus subject areas

  • Signal Processing
  • Computer Networks and Communications

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

  • Cite this

    Wu, Y., Xu, J., & Hajek, B. (2016). Achieving exact cluster recovery threshold via semidefinite programming under the stochastic block model. In M. B. Matthews (Ed.), Conference Record of the 49th Asilomar Conference on Signals, Systems and Computers, ACSSC 2015 (pp. 1070-1074). [7421303] (Conference Record - Asilomar Conference on Signals, Systems and Computers; Vol. 2016-February). IEEE Computer Society. https://doi.org/10.1109/ACSSC.2015.7421303