A stochastic block model is a random graph model in which vertices receive block labels and graph edges
occur independently with probabilities determined by the labels of their endpoints.
For labels 
and a symmetric matrix of probabilities ![P in [0,1]^(q×q)](/images/equations/StochasticBlockModel/Inline2.svg)
, the adjacency
matrix entries satisfy
 |
The model is assortative when within-block edges tend to be more likely than between-block edges and disassortative when the reverse holds. The special case with equal-sized blocks, one within-block probability, and one between-block probability is often called the planted partition model.
For sparse graphs, the probabilities are commonly scaled as 
,
so expected vertex degrees remain bounded as the
number 
of vertices grows. Given only the generated graph, community
detection seeks to estimate the hidden labels. In the equal-sized symmetric model
with 
and 
for 
,
a central spectral detectability boundary is
![(c_(in)-c_(out))^2=q[c_(in)+(q-1)c_(out)].](/images/equations/StochasticBlockModel/NumberedEquation2.svg) |
Above this boundary, suitable spectral methods produce labels correlated with the planted labels. For two blocks, the same boundary separates possible from impossible detection in the sparse symmetric model. For more blocks, the relationship between spectral, computational, and information-theoretic boundaries depends on the model parameters (Abbe 2018).
Replacing pairwise edge probabilities by higher-order connection tensors gives the hypergraph stochastic block model.
