---
kind: concept
slug: stochastic-block-model
title: Stochastic block model
summary: >-
  A latent-group graph model: each node has a hidden group, and edge probability depends only on the pair of groups. A review covers degree-corrected, valued, mixed-membership, overlapping, dynamic, text and nested variants, plus fitting and choosing the number of groups. Two GNN papers use a contextual and a signed-directed variant as synthetic benchmarks.
tags: [graph-clustering, network-analysis, latent-variable-model, review, synthetic-benchmark, signed-graph]
papers: ["1903.00114", "2006.07988", "2209.00546"]
related: [community-detection, expectation-maximization, model-selection, spectral-clustering, spectral-methods, topic-modelling, graph-neural-network, generalized-pagerank]
status: draft
updated_at: 2026-11-01
---

## Overview

A stochastic block model (SBM) explains an observed graph by hidden group
labels. Each node has one group, and each pair of nodes is linked with a
probability that depends only on the two groups [arxiv:1903.00114 §2]. Fitting
the model means inferring the group memberships and the block matrix of
group-pair probabilities at once, without any labels given in advance
[arxiv:1903.00114 §1].

The review treats every variant as a change to one of a few parts: the graph
type (binary, valued, signed), whether node degrees are corrected for, hard or
soft membership, the inference method, how the number of groups is chosen,
and whether time or text is added [arxiv:1903.00114 §3–§11]. The review
covers the variants under Variants except the last two. The contextual SBM
comes from a graph neural network paper, which uses it to generate benchmark
graphs rather than to model data [arxiv:2006.07988 §5]. A second GNN paper
defines a signed, directed variant and uses it the same way
[arxiv:2209.00546 §4.2]. The review runs no experiments; the GNN papers'
results measure node classifiers and node clusterers, not fits of the SBM.

## Variants

### Bernoulli SBM

The base model. Dyads are independent Bernoulli draws given the groups, with
success probability Z_pᵀ C Z_q, where C is the symmetric block matrix for
undirected graphs [arxiv:1903.00114 §2] [eq. 2]. Nodes in one group are
stochastically equivalent: they have the same edge distribution toward any
third node. This does not mean that nodes in a group link more to each other
[arxiv:1903.00114 §2.1]. Card: [A Review of Stochastic Block Models and Extensions for Graph Clustering](/papers/1903.00114).

### Degree-corrected SBM (DC-SBM)

Multiplies the expected edge count by a per-node parameter φ_p, with φ summing
to one within each group [arxiv:1903.00114 §3.3] [eq. 7]. It is aimed at
graphs where degrees vary a lot inside a group. The review gives the maximum
likelihood estimates: φ_p is node p's degree divided by its group's total
degree, and C_ij is the number of edges between groups i and j
[arxiv:1903.00114 §3.3]. On the karate club network the DC-SBM recovers the
two known factions, and the plain SBM does not [arxiv:1903.00114 §8.1]. See
[Contradictions](#contradictions) for the likelihood-ratio result on the same
network.

### Poisson and valued SBMs

For weighted or count-valued edges. The Poisson SBM has expected edge count
Z_pᵀ C Z_q [arxiv:1903.00114 §3.3] [eq. 6]. The review says it is asymptotically
equivalent to the Bernoulli model for large sparse graphs, with no convergence
rate given [arxiv:1903.00114 §3.3]. A collapsed Poisson variant integrates out
C under Gamma priors [arxiv:1903.00114 §3.3] [eq. 9]. Valued graphs have other
forms too: signed directed edges with values in {−1, 0, 1}, a tournament form
for win, loss and tie, and a geometric or unbounded-rate exponential link
[arxiv:1903.00114 §3.2]. Zeros are ambiguous in valued data: they may mean no
edge, a zero-weight edge, or missing data [arxiv:1903.00114 §3.3].

### Microcanonical and nonparametric SBM

Puts an exponential prior on each C_ij with rate N_iN_j/λ. Integrating out C
leaves a likelihood that depends on the memberships only through the edge
counts E and dyad counts N [arxiv:1903.00114 §3.4] [eq. 11]. Integrating out λ
as well leaves a model with no free parameters, which the review calls
nonparametric because it also models K [arxiv:1903.00114 §3.4] [eq. 12]. The
same construction applied to the DC-SBM gives a microcanonical DC-SBM
[arxiv:1903.00114 §3.4].

### Mixed-membership SBM (MMSBM)

Soft clustering: each node has a membership vector θ_p, and each dyad draws
its own latent group indicators from the two endpoints' vectors
[arxiv:1903.00114 §4.1] [eq. 15]. Inference targets the membership vectors,
not the pairwise indicators [arxiv:1903.00114 §4.1]. The review cites the
authors of the variational method as claiming a cost of O(nK+2K), against
O(n²) for MCMC [arxiv:1903.00114 §6.2]. The review does not measure this.

### Overlapping SBM

Each node picks a non-empty subset of the K groups, giving 2^K − 1 choices per
node [arxiv:1903.00114 §4.2]. The review reports that overlapping nodes in real
networks usually belong to two or three groups and make up less than 30% of
nodes, and that the model overfits more easily than the non-overlapping one
[arxiv:1903.00114 §4.2].

### Longitudinal (dynamic) SBM

Lets memberships or block parameters change over time. The review lists
state-space models of membership or block parameters, Markov chains over
memberships, autoregressive continuous-time chains on dyads, and Poisson
processes on interaction events [arxiv:1903.00114 §9]. When C varies over
time, identifiability and label switching become issues [arxiv:1903.00114 §9].
The review also cites a detectability threshold below which no efficient
algorithm beats chance [arxiv:1903.00114 §9].

### SBM with topic models

Adds text. In the textual-edge case the text sits on the edges, and the
stochastic topic block model (STBM) gives each pair of groups its own topic
mixture [arxiv:1903.00114 §11.1.1]. In the textual-node case the text sits on
the nodes, as with linked documents [arxiv:1903.00114 §11.1.2]. The
[topic-modelling](/concepts/topic-modelling) concept covers the topic-model
side. Entries for each model are in [tab. 4] of the review.

### Nested SBM

A hierarchy: an SBM is fitted to the groups of the level below. In a synthetic
example of 64 cliques of 10 nodes, a flat microcanonical SBM settled on 32
groups, while the nested model recovered the hierarchy [arxiv:1903.00114 §7.2.1].
On the political blogs network under the DC-SBM, the lowest level has 20
groups inside two main factions [arxiv:1903.00114 §8.1].

### Contextual SBM (cSBM) for benchmarks

An SBM whose nodes also carry features, used to build synthetic node
classification graphs. The GNN paper uses two equal classes, n = 5000 nodes,
f = 2000 features, ξ = n/f = 2.5 and margin ε = 3.25 [arxiv:2006.07988 app. A.5].
Homophily is set by one knob φ: φ = (2/π)·arctan(λ√ξ/μ), with
λ² + μ²/ξ = 1 + ε [arxiv:2006.07988 §5] [app. A.5]. The paper sweeps φ from
−1 to 1 in its tables [tab. 5] [tab. 6]. Average degree is not stated in the
paper [arxiv:2006.07988 app. A.5]. The paper also uses real heterophilic
benchmarks, so the synthetic graphs are a control, not a replacement
[arxiv:2006.07988 §5]. Card: [Adaptive Universal Generalized PageRank Graph Neural Network](/papers/2006.07988).

### Signed directed SBM (SDSBM) for benchmarks

An SBM whose edges carry a sign and a direction. The generator takes a
meta-graph F of C blocks, an edge rate p, a node count n, a block-size ratio ρ
and a sign-flip noise level η. Each directed edge from block k to block l is
drawn with probability p·|F_kl| and gets weight +1 or −1 from the sign of F_kl.
Then every edge's sign is flipped with probability η [arxiv:2209.00546 §4.2].
The paper uses two meta-graphs, with three and four blocks, and a directional
noise level γ between 0 and 0.5 [arxiv:2209.00546 §4.2]. It says the model
generalises the signed SBM and the directed SBM of earlier work when the
meta-graph is chosen suitably [arxiv:2209.00546 §4.2]. Node clustering with
MSGNN on these graphs is reported as ARI in figures, not tables. The paper
says MSGNN beats SigMaNet on every synthetic set and is competitive with
SSSNET, and that a nonzero charge q usually helps on SDSBM
[arxiv:2209.00546 §4.4.1]. Card: [MSGNN](/papers/2209.00546).

## Inference

- **Monte Carlo.** Plain Gibbs samplers update every parameter and latent
  variable in turn. The review also names Hamiltonian Monte Carlo, applied to
  a transformed C, and stochastic-gradient MCMC, which uses mini-batches of
  nodes and gains scalability from graph sparsity [arxiv:1903.00114 §6.1].
- **Collapsed samplers.** A collapsed sampler picks one of four moves at random
  each iteration: a single-node Gibbs move, a reassignment of two random groups,
  or a move that adds or removes a group [arxiv:1903.00114 §6.1.1].
- **Variational EM.** Maximises a lower bound on the marginal log-likelihood
  with a factorised distribution over the latent variables; the E step tightens
  the bound and the M step updates the parameters [arxiv:1903.00114 §6.2]
  [eq. 23] [eq. 24].
- **Greedy.** Moves one node at a time, keeps the best objective seen, restarts
  from it, and stops when no move raises the objective [arxiv:1903.00114 §6.3].
- **Belief propagation.** Used by Decelle et al. for a binary directed model
  [arxiv:1903.00114 tab. 1].

## Choosing K

- **Fit and score.** Fit several K and compare them with a criterion. The
  review lists the approximate ICL [eq. 25] for directed graphs, the exact ICL
  under conjugate priors, a variational bound used as marginal likelihood,
  penalised likelihoods, held-out perplexity and an elbow plot of k-means
  distances [arxiv:1903.00114 §7.1]. It says BIC is intractable here, because
  the observed-data likelihood it needs is not available [arxiv:1903.00114 §7.1].
- **Let the model decide.** A Dirichlet process or hierarchical Dirichlet
  process over memberships, or an Indian buffet process for latent features,
  generates K [arxiv:1903.00114 §7.2]. Birth, death, split and merge moves
  change K during MCMC [arxiv:1903.00114 §7.2].

## When to use which

| Situation | Use | Why |
|---|---|---|
| Binary graph, one group per node, roughly uniform degrees | Bernoulli SBM | Simplest model; the review's base case [arxiv:1903.00114 §2] |
| Strong degree differences inside groups | DC-SBM | Built to absorb degree variation [arxiv:1903.00114 §3.3]. The review reports a case where the likelihood-ratio test did not support it [arxiv:1903.00114 §8.1] |
| Weighted or count edges | Poisson or valued SBM | Edge models for valued data [arxiv:1903.00114 §3.2] [§3.3] |
| Nodes that may belong to several groups | MMSBM or overlapping SBM | Soft membership [arxiv:1903.00114 §4.1] [§4.2]. Soft clustering needs O(n²) latent variables against O(n) for hard clustering [arxiv:1903.00114 §6]; the overlapping model is prone to overfitting [arxiv:1903.00114 §4.2] |
| Large graph, memory or time limited | Hard clustering with variational EM or greedy search | The review says soft clustering costs more [arxiv:1903.00114 §6]. Stochastic-gradient MCMC scales with sparsity [arxiv:1903.00114 §6.1] |
| Number of groups unknown and no criterion wanted | Nonparametric microcanonical SBM, DP/HDP prior, or nested SBM | Models K directly [arxiv:1903.00114 §3.4] [§7.2] [§7.2.1] |
| Network changes over time | Longitudinal SBM | Time-varying membership or block parameters [arxiv:1903.00114 §9] |
| Need node-classification graphs with a known, adjustable homophily level | Contextual SBM | The φ knob runs over the full range in the GNN paper's sweeps [arxiv:2006.07988 §5] [tab. 5]. Synthetic graphs do not show accuracy on real data, so pair them with real benchmarks [arxiv:2006.07988 §5] |
| Signed, directed edges, and a synthetic test with known blocks | SDSBM generator | Sign and direction noise are set by η and γ [arxiv:2209.00546 §4.2]. Use it for clustering tests, not for fitting real networks |
| Text on edges or nodes | SBM with topic models (e.g. STBM) | Joint groups and topics [arxiv:1903.00114 §11] |
| Only the node groups are needed, not a generative fit | Community detection methods | The review lists modularity and label propagation as non-probabilistic alternatives [arxiv:1903.00114 §5.4.2]; see [community-detection](/concepts/community-detection) |

The review's own comparison tables classify each model by graph type,
directedness, inference, clustering and number of groups; they are
classifications, not measured results [arxiv:1903.00114 tab. 1] [tab. 2]
[tab. 3] [tab. 4].

## Implementation sketch

Generative side: sample memberships from the group probabilities, then draw
each dyad as a Bernoulli trial with the block entry for its two groups. This
is the base model; variants change the draw.

```pseudocode
# Sample an undirected Bernoulli SBM  [arxiv:1903.00114 §2] [eq. 2] [eq. 4]
# Input:  theta (K,) group probabilities summing to 1
#         C (K, K) symmetric block matrix with entries in [0, 1]
#         n number of nodes
# Output: memberships (n,) with values 0..K-1; adjacency Y (n, n)

def sample_sbm(n, theta, C):
    # Draw each node's hidden group from a multinomial  [arxiv:1903.00114 §2] [eq. 4]
    memberships = draw_categorical(theta, size=n)
    adjacency = zeros(n, n)
    # Each dyad is an independent Bernoulli draw given the groups  [arxiv:1903.00114 §2]
    for p in range(n):
        for q in range(p + 1, n):
            # The edge rate is the block entry for the two groups  [arxiv:1903.00114 §2]
            rate = C[memberships[p], memberships[q]]
            adjacency[p, q] = draw_bernoulli(rate)
            adjacency[q, p] = adjacency[p, q]
    return memberships, adjacency
```

Fitting side: for each candidate K, run a greedy label-switching search and
keep the best objective. Then pick K by a criterion. The dyad count for
two different groups is the product of their sizes; see the first pitfall
under [Contradictions](#contradictions).

```pseudocode
# Greedy fit for a fixed K, then choose K by a criterion  [arxiv:1903.00114 §6.3] [§7.1]
# Input:  adjacency Y (n, n); candidate values ks; objective(labels, Y, K)
# Output: best labels and K

def fit_sbm(Y, ks):
    best = None
    for K in ks:
        # Start from an initial labelling into K groups  [arxiv:1903.00114 §6.3]
        labels = initial_labels(n_nodes(Y), K)
        # Move one node at a time; stop when no move raises the objective  [arxiv:1903.00114 §6.3]
        labels = greedy_label_switch(labels, Y, K, objective)
        # Score this K with a criterion such as ICL  [arxiv:1903.00114 §7.1]
        score = criterion(labels, Y, K)
        if best is None or score > best.score:
            best = Result(labels, K, score)
    return best
```

## Contradictions

- **Group counts in text versus table.** The text says Tallberg used K = 2 and
  Karrer & Newman used K = 3 [arxiv:1903.00114 §7]. Table 1 lists Tallberg as
  Fixed (3) and Karrer & Newman as Fixed (2) [arxiv:1903.00114 tab. 1]. Check
  the source before using either value.
- **Karate club, degree correction.** The DC-SBM recovers the two known factions
  and the plain SBM does not [arxiv:1903.00114 §8.1]. A likelihood-ratio test on
  the same network finds no clear evidence for degree correction, though degree
  heterogeneity prompted it [arxiv:1903.00114 §8.1]. The review reports both
  without resolving them.
- **Karate club, selected K.** Under the DC-SBM, the ICL selects K = 1; under the
  plain SBM it selects K = 4, with groups following degree levels
  [arxiv:1903.00114 §8.1]. Decelle et al. and Newman & Reinert both find K = 2 as
  the best fit [arxiv:1903.00114 §8.1].
- **Political blogs, selected K.** A penalised likelihood selects K = 4, where
  one label group splits into three inferred groups. At another tuning value it
  selects K = 1, which the review says motivates a corrected BIC with a heavier
  penalty [arxiv:1903.00114 §8.1].
- **Latent feature models labelled hard.** The review says a latent-feature node
  can have several 1s, unlike hard SBM membership [arxiv:1903.00114 §5.1], yet
  Table 1 labels the two latent-feature models as Hard [arxiv:1903.00114 tab. 1].
- **Dyad count for different groups.** The text gives N_ij = N_iN_j/2 for i ≠ j
  [arxiv:1903.00114 §2] [eq. 3]. The review's example densities match dividing
  by N_iN_j instead: 37/(25·30) ≈ 0.049 for groups 1 and 2, and 36/(25·35) ≈ 0.041
  for groups 1 and 3 [arxiv:1903.00114 §2]. Dividing by N_iN_j/2 would give
  about 0.099 for groups 1 and 2. Implementations should follow the example.
- **Results are not comparable across papers.** Studies use different networks,
  sizes and criteria, so their outcomes differ for reasons beyond the model
  [arxiv:1903.00114 §11.4] [§12.1].

## Papers

- [A Review of Stochastic Block Models and Extensions for Graph Clustering](/papers/1903.00114): a survey of SBM variants, inference methods and ways to choose K, with four comparison tables and no experiments of its own.
- [Adaptive Universal Generalized PageRank Graph Neural Network](/papers/2006.07988): uses a contextual SBM with a homophily knob to generate the synthetic graphs for its node-classification experiments.
- [MSGNN](/papers/2209.00546): a signed, directed spectral GNN. It defines the signed directed SBM and uses it, with two older signed SBMs, for node-clustering tests.