Reconstruction in the Labeled Stochastic Block Model

Marc Lelarge 1, 2, 3 Laurent Massoulié 4 Jiaming Xu 5
1 DYOGENE - Dynamics of Geometric Networks
DI-ENS - Département d'informatique de l'École normale supérieure, ENS Paris - École normale supérieure - Paris, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR8548
Abstract : The labeled stochastic block model is a random graph model representing networks with community structure and interactions of multiple types. In its simplest form, it consists of two communities of approximately equal size, and the edges are drawn and labeled at random with probability depending on whether their two endpoints belong to the same community or not. It has been conjectured in [1] that this model exhibits a phase transition: reconstruction (i.e. identification of a partition positively correlated with the "true partition" into the underlying communities) would be feasible if and only if a model parameter exceeds a threshold. We prove one half of this conjecture, i.e., reconstruction is impossible when below the threshold. In the converse direction, we introduce a suitably weighted graph. We show that when above the threshold by a specific constant, reconstruction is achieved by (1) minimum bisection, and (2) a spectral method combined with removal of nodes of high degree.
Type de document :
Communication dans un congrès
IEEE Information Theory Workshop, Sep 2013, Seville, Spain. 2013
Liste complète des métadonnées
Contributeur : Marc Lelarge <>
Soumis le : mercredi 11 décembre 2013 - 18:46:50
Dernière modification le : jeudi 11 janvier 2018 - 06:25:34


  • HAL Id : hal-00917425, version 1



Marc Lelarge, Laurent Massoulié, Jiaming Xu. Reconstruction in the Labeled Stochastic Block Model. IEEE Information Theory Workshop, Sep 2013, Seville, Spain. 2013. 〈hal-00917425〉



Consultations de la notice