Multisection in the Stochastic Block Model using Semidefinite Programming

We consider the problem of identifying underlying community-like structures in graphs. Towards 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 p = fracα log(m)m and q = fracβ log(m)m we show that a certain natural SDP based algorithm solves the problem of em exact recovery in the k-community SBM, with high probability, whenever √α - √β > √1, as long as k=o(log n). This threshold is known to be the information theoretically optimal. We also study the case when k=θ(log(n)). In this case however we achieve recovery guarantees that no longer match the optimal condition √α - √β > √1, thus leaving achieving optimality for this range an open question.