  The stochastic block model is a natural model for studying community
detection in random networks. Its clustering properties have been extensively
studied in the statistics, physics and computer science literature. Recently
this area has experienced major mathematical breakthroughs, particularly for
the binary (two-community) version, see Mossel, Neeman, Sly (2012, 2013) and
Massoulie (2013). In this paper, we introduce a variant of the binary model
which we call the regular stochastic block model (RSBM). We prove rigidity by
showing that with high probability an exact recovery of the community structure
is possible. Spectral methods exhibit a regime where this can be done
efficiently. Moreover we also prove that, in this setting, any suitably good
partial recovery can be bootstrapped to obtain a full recovery of the
communities.
