## Connecting communities via the block model

### Edited by org.aimpl.user:awein@mit.edu

The stochastic block model is a generative model for random graphs with community structure. A simple variant is the following. Let each of the $n$ vertices have a community assignment chosen independently and uniformly from $[k]$. For each pair of nodes: if they are in the same community, add an edge between them with probability $p$; otherwise add an edge between them with probability $q$. We now consider the inference problem in which we are given this graph and want to identify the communities (either exactly or approximately).

### Sections

Cite this as: *AimPL: Connecting communities via the block model, available at http://aimpl.org/blockmodel.
*