Multisection in the Stochastic Block Model using Semidefinite Programming

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