Exploiting Tradeoffs for Exact Recovery in Heterogeneous Stochastic Block Models

The Stochastic Block Model (SBM) is a widely used random grap h model for networks with communities. Despite the recent burst of inte rest in community detection under the SBM from statistical and computational points of view, there are still gaps in understanding the fundamental limits of re covery. In this paper, we consider the SBM in its full generality, where there is no r estriction on the number and sizes of communities or how they grow with the numb er of nodes, as well as on the connectivity probabilities inside or across c ommunities. For such stochastic block models, we provide guarantees for exact re covery via a semidef-inite program as well as upper and lower bounds on SBM paramet ers for exact recoverability. Our results exploit the tradeoffs among th e various parameters of heterogenous SBM and provide recovery guarantees for man y new interesting SBM configurations.