Community Detection in the Stochastic Block Model: Approximate Belief Propagation

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.

日期：
演讲者：
Colin Sandon
所属机构：
Princeton University