Affordable Access

Recovery and Rigidity in a Regular Stochastic Block Model

Authors
  • Brito, Gerandy
  • Dumitriu, Ioana
  • Ganguly, Shirshendu
  • Hoffman, Christopher
  • Tran, Linh V.
Type
Preprint
Publication Date
Oct 17, 2015
Submission Date
Jul 03, 2015
Identifiers
arXiv ID: 1507.00930
Source
arXiv
License
Yellow
External links

Abstract

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.

Report this publication

Statistics

Seen <100 times