Skip navigation
Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp011v53k058n
Title: Community Detection in the Stochastic Block Model: fundamental limits
Authors: Sandon, Colin Peter
Advisors: Abbe, Emmanuel A
Contributors: Mathematics Department
Keywords: clustering
graph
Subjects: Mathematics
Computer science
Issue Date: 2017
Publisher: Princeton, NJ : Princeton University
Abstract: In recent years, there have been many developments in the study of the stochastic block model, starting with a paper by Decelle et al. in which they conjecture that in the sparse stochastic block model, efficient community detection is possible if and only if the parameters are above the Kesten-Stigum bound. Massouli\'e , Mossel et al., and Bordenave et al. succeeded in proving the positive half of this conjecture in the $2$-community symmetric case. Also, Mossel et al. proved that community detection is impossible below the KS bound in the $2$-community symmetric case. On another note, Abbe et al. and Mossel et al. found a threshold for when it was possible to completely recover the communities in the $2$-community symmetric case. In this thesis, we go beyond the $2$-community symmetric case to prove the positive half of the conjecture for the general SBM. In order to do that, we construct a linearized belief propagation algorithm that runs in $O(n\log n)$ time and prove that it detects communities whenever the parameters of the SBM are above the KS bound. We also prove that unlike in the $2$-community symmetric case, in the general SBM there are choices of parameters below the KS threshold for which one can detect communities in exponential time, confirming another conjecture by Decelle et al. This result implies that we cannot prove the impossibility of efficient community detection below the KS bound without proving some major conjectures on what compuations can be done efficiently. We also extend the threshold for when it is possible to completely recover the communities to the general SBM.
URI: http://arks.princeton.edu/ark:/88435/dsp011v53k058n
Alternate format: The Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the library's main catalog: catalog.princeton.edu
Type of Material: Academic dissertations (Ph.D.)
Language: en
Appears in Collections:Mathematics

Files in This Item:
File Description SizeFormat 
Sandon_princeton_0181D_12177.pdf822.48 kBAdobe PDFView/Download


Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.