Community Detection in the Stochastic Block Model: Approximate Belief Propagation
1,710 views · Published 10 January 2017 · 46:46 · Indexed 25 September 2026
Channel: Microsoft Research · 2017 · Science & Technology
The 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/
