Skip to yearly menu bar Skip to main content


Exploiting Tradeoffs for Exact Recovery in Heterogeneous Stochastic Block Models

Amin Jalali · Qiyang Han · Ioana Dumitriu · Maryam Fazel

Area 5+6+7+8 #53

Keywords: [ Model Selection and Structure Learning ] [ Graph-based Learning ] [ Convex Optimization ] [ Large Scale Learning and Big Data ] [ Clustering ]


The Stochastic Block Model (SBM) is a widely used random graph model for networks with communities. Despite the recent burst of interest in community detection under the SBM from statistical and computational points of view, there are still gaps in understanding the fundamental limits of recovery. In this paper, we consider the SBM in its full generality, where there is no restriction on the number and sizes of communities or how they grow with the number of nodes, as well as on the connectivity probabilities inside or across communities. For such stochastic block models, we provide guarantees for exact recovery via a semidefinite program as well as upper and lower bounds on SBM parameters for exact recoverability. Our results exploit the tradeoffs among the various parameters of heterogenous SBM and provide recovery guarantees for many new interesting SBM configurations.

Live content is unavailable. Log in and register to view live content