2015/07/08 by Agarwal, Naman, Bandeira, Afonso S., Koiliaris, Konstantinos +1
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Probability (math.PR)
paper · doi:10.48550/arxiv.1507.02323
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 = (αlog(m))/(m) and q = (β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.