Multisection in the Stochastic Block Model using Semidefinite Programming

MaRDI QIDQ6263429zbMATH OpenFDO

Authors Naman Agarwal, Afonso S. Bandeira, Konstantinos Koiliaris, Alexandra Kolla

Publication date 8 July 2015

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=fracalphalog(m)m$ and $$ 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 $$, as long as $k=o(logn)$. This threshold is known to be the information theoretically optimal. We also study the case when $k=heta(log(n))$. In this case however we achieve recovery guarantees that no longer match the optimal condition $$, thus leaving achieving optimality for this range an open question.

This page was built for publication: Multisection in the Stochastic Block Model using Semidefinite Programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6263429)