Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions

Bruce Hajek, Yihong Wu, Jiaming Xu

Research output: Contribution to journalArticle

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 (SBM) of two equal-sized clusters. The same was shown for the case of a single cluster and outliers. Extending the proof techniques, in this paper, it is shown that SDP relaxations also achieve the sharp recovery threshold in the following cases: 1) binary SBM with two clusters of sizes proportional to network size but not necessarily equal; 2) SBM with a fixed number of equal-sized clusters; and 3) binary censored block model with the background graph being Erd's-Rényi. Furthermore, a sufficient condition is given for an SDP procedure to achieve exact recovery for the general case of a fixed number of clusters plus outliers. These results demonstrate the versatility of SDP relaxation as a simple, general purpose, computationally feasible methodology for community detection.

Original languageEnglish (US)
Article number7523889
Pages (from-to)5918-5937
Number of pages20
JournalIEEE Transactions on Information Theory
Volume62
Issue number10
DOIs
StatePublished - Oct 2016

    Fingerprint

Keywords

  • Community detection
  • Erd's-Rényi random graph
  • Semidefinite programming
  • Stochastic block model

ASJC Scopus subject areas

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

Cite this