Stochastic Block Model

The stochastic block model is a statistical problem where the goal is to recover a community structure from a graph. The model is defined by a graph G with vertex set [n] = {1,..., n}, with edges drawn independently as follows: for vertices u, v, we have u ∼ v with probability a/n if σuσv = 1, and probability b/n if σuσv = −1.