Multisection in the Stochastic Block Model using Semidefinite Programming

Abstract

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 = (m)m and q = (m)m we show that a certain natural SDP based algorithm solves the problem of exact recovery in the k-community SBM, with high probability, whenever - > 1, as long as k=o( n). This threshold is known to be the information theoretically optimal. We also study the case when k=((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.

Tasks

Reproductions