Detecting planted communities in random graphs

The stochastic block model (aka. planted partition model) is a popular model for representing networks with communities. Elchanan Mossel, Joe Neeman, and Allan Sly have been investigating algorithms and fundamental limits for detecting and recovering these communities. They established sharp transitions for the problem of extracting non-trivial informationĀ and the problem of exactly recovering communities. They also gave a new algorithm that obtains provably optimal accuracy for the problem of detecting communities in “Consistency thresholds for the planted bisection model” and “Belief propagation, robust reconstruction, and optimal recovery of block models“.