SCIENCE@home

Multisection in the Stochastic Block Model using Semidefinite Programming

Naman Agarwal,A. Bandeira,Konstantinos Koiliaris,A. Kolla

Published 2015 in arXiv.org

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 \(p = \frac {\alpha \log (m)}{m}\) and \(q = \frac {\beta \log (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 \(\sqrt {\alpha } - \sqrt {\beta } > \sqrt {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=\theta (\log (n))\). In this case however, we achieve recovery guarantees that no longer match the optimal condition \(\sqrt {\alpha } - \sqrt {\beta } > \sqrt {1}\), thus leaving achieving optimality for this range an open question.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-29 of 29 references · Page 1 of 1

CITED BY

Showing 1-60 of 60 citing papers · Page 1 of 1