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: clusteringgraph Subjects: MathematicsComputer 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