Reconstructability and Distinguishability of Sparse Stochastic Block Models

• Activity Number: 223
• Type: Topic Contributed
• Date/Time: Monday, August 4, 2014 : 2:00 PM to 3:50 PM
• Sponsor: IMS
• Author(s): Praneeth Netrapalli*+ and Joe Neeman
• Companies: University of Texas at Austin and University of Texas at Austin
• Keywords: Stochastic block model ; Reconstruction ; Clustering ; Planted partition model

Abstract

We consider the sparse stochastic block model, a popular model for random graphs with community structure. We show that for a certain range of parameters the community structure can be detected, while for another range of parameters it can neither be detected, nor reconstructed. In the case where there are only two communities of equal size, our results recover the sharp bounds due to Mossel et al., who studied that special case.