Community Detection in the Stochastic Block Model: Approximate Belief Propagation
3The stochastic block model is one of the simplest models for a random graph with different types of vertices, known as communities. In this talk I will describe an efficient algorithm that distinguishes between vertices from different communities with nontrivial accuracy whenever the SBM's parameters are above the Kesten-Stigum threshold, proving half of a conjecture by Decelle et al. I will also show that given exponential time it is sometimes possible to distinguish between communities with nontrivial accuracy below the KS threshold. Furthermore, I will also discuss how accurately one can classify vertices when the signal to noise ratio of the graph is large.
See more on this video at https://www.microsoft.com/en-us/research/video/community-detection-stochastic-block-model-approximate-belief-propagation/