@inbook{4e8afb8f97144fcfad93807c72df04a6,

title = "Multisection in the stochastic block model using semidefinite programming",

abstract = "We consider the problem of identifying underlying community-like structures in graphs. Toward this end, we study the stochastic block model (SBM) on k-clusters: a random model on n = km vertices, partitioned in k equal sized clusters, with edges sampled independently across clusters with probability q and within clusters with probability p, p > q. The goal is to recover the initial “hidden” partition of [n]. We study semidefinite programming (SDP)-based algorithms in this context. In the regime (formula presented), we show that a certain natural SDP-based algorithm solves the problem of exact recovery in the k-community SBM, with high probability, whenever (formula presented), as long as k= o(log n). This threshold is known to be the information theoretically optimal. We also study the case when (formula presented). In this case however, we achieve recovery guarantees that no longer match the optimal condition (formula presented), thus leaving achieving optimality for this range an open question.",

keywords = "Dual certificate, Graph partitioning, Random models, Semidefinite programming, Stochastic block model",

author = "Naman Agarwal and Bandeira, {Afonso S.} and Konstantinos Koiliaris and Alexandra Kolla",

note = "Funding Information: Acknowledgements Most of the work presented in this paper was conducted while ASB was at Princeton University and partly conducted while ASB was at the Massachusetts Institute of Technology. ASB acknowledges support from AFOSR Grant No. FA9550-12-1-0317, NSF DMS-1317308, NSF DMS-1712730, and NSF DMS-1719545. Funding Information: Most of the work presented in this paper was conducted while ASB was at Princeton University and partly conducted while ASB was at the Massachusetts Institute of Technology. ASB acknowledges support from AFOSR Grant No. FA9550-12-1-0317, NSFDMS-1317308, NSFDMS-1712730, and NSFDMS-1719545. Publisher Copyright: {\textcopyright} Springer International Publishing AG 2017.",

year = "2017",

doi = "10.1007/978-3-319-69802-1_4",

language = "English (US)",

series = "Applied and Numerical Harmonic Analysis",

publisher = "Springer International Publishing",

number = "9783319698014",

pages = "125--162",

booktitle = "Applied and Numerical Harmonic Analysis",

edition = "9783319698014",

}