Community Detection in the Stochastic Block Model: Approximate Belief Propagation

Опубликовано 10 января 2017, 17:57

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 microsoft.com/en-us/research/v...