Stochastic Block Model — Probabilistic Community Detection in Networks
Also known as: SBM, degree-corrected SBM, DCSBM, Stokastik Blok Modeli (SBM)
The Stochastic Block Model (SBM), introduced by Holland, Laskey and Leinhardt (1983), is a probabilistic generative model for graphs that assigns nodes to latent blocks and parametrically estimates the connection probabilities between blocks. It is the foundational approach for community detection, core-periphery identification, and hierarchical structure discovery in network analysis.
Key highlights
- Principled probabilistic framework that allows model selection via BIC or Bayes factor, avoiding arbitrary parameter choices.
- Accommodates a wide range of structural patterns — communities, core-periphery, bipartite, and hierarchical — beyond the dense-clique assumption of algorithmic methods.
- The Degree-Corrected variant handles graphs with heterogeneous degree distributions and hubs without distorting the block assignments.
- Provides posterior membership probabilities, enabling soft or uncertain node assignments rather than hard partitions.
Intuition
This section is available to Pro members. Upgrade to Pro
How it works
This section is available to Pro members. Upgrade to Pro
When to use it
Use the Stochastic Block Model when you have a network with at least 50 nodes and you want to discover latent group structure without assuming that groups must be dense cliques. It is appropriate for directed or undirected graphs, weighted or unweighted, and suits exploratory as well as classification tasks. The DCSBM variant is preferred when node degrees vary substantially. If the graph has fewer than 20 nodes, community structure cannot be reliably estimated and simpler descriptive metrics should be used instead. Assumptions: block memberships are latent and not observed; the block connection matrix is assumed homogeneous within each block pair; and K must be selected by BIC or Bayes factor rather than fixed arbitrarily.
Strengths & limitations
- Principled probabilistic framework that allows model selection via BIC or Bayes factor, avoiding arbitrary parameter choices.
- Accommodates a wide range of structural patterns — communities, core-periphery, bipartite, and hierarchical — beyond the dense-clique assumption of algorithmic methods.
- The Degree-Corrected variant handles graphs with heterogeneous degree distributions and hubs without distorting the block assignments.
- Provides posterior membership probabilities, enabling soft or uncertain node assignments rather than hard partitions.
- Requires at least around 50 nodes for reliable block estimation; very small graphs yield unstable solutions.
- Inference is computationally expensive for large graphs: variational EM or MCMC is required, and convergence is not guaranteed.
- The basic SBM's homogeneity assumption within block pairs breaks down when within-block connection rates vary — the DCSBM mitigates but does not eliminate this.
- Block selection via BIC or Bayes factor can still under- or over-segment if the graph has weakly separated communities.
Common pitfalls
This section is available to Pro members. Upgrade to Pro
Applications
This section is available to Pro members. Upgrade to Pro
Frequently asked
How is the Stochastic Block Model different from modularity-based community detection?
Modularity maximisation (e.g., Louvain, Leiden) optimises a heuristic objective that implicitly assumes assortative, roughly equal-sized communities and has a known resolution limit that prevents detection of small communities. The SBM is a generative probabilistic model with explicit assumptions; block count is chosen by model selection (BIC or Bayes factor) rather than heuristic optimisation, and it can detect disassortative and core-periphery structures that modularity-based methods miss.
When should I use DCSBM instead of the basic SBM?
Use DCSBM when the node degree distribution is heterogeneous — for example when a small number of hubs account for a large fraction of edges, or when the degree sequence follows an approximate power law. The basic SBM treats all nodes within a block as exchangeable, which causes hubs to be pulled into their own spurious blocks. DCSBM adds a degree correction term that separates structural position from degree, producing more interpretable block assignments in such graphs.
How do I choose the number of blocks K?
Fit models for a range of K values and select the one that minimises BIC or maximises the Bayes factor (or equivalently minimises description length). Do not choose K based on visual inspection of the graph or prior expectations. Most implementations (graph-tool, blockmodels in R) automate this search. Sensitivity analysis — checking whether the qualitative block structure changes when K is varied by one — is also recommended.
What is the minimum network size for SBM to be reliable?
The registry specifies a minimum of 50 nodes for reliable inference. With fewer than 20 nodes the model cannot identify meaningful community structure and will fit noise — use descriptive network statistics or simple community detection instead. Between 20 and 50 nodes results should be treated as exploratory and interpreted with caution.
Sources
- 1.Holland, P.W., Laskey, K.B. & Leinhardt, S. (1983). Stochastic Blockmodels: First Steps. Social Networks, 5(2), 109-137.
- 2.Lee, C. & Wilkinson, D.J. (2019). A Review of Stochastic Block Models and Extensions for Graph Clustering. Applied Network Science, 4(1), 122.
You have read it. What now?
Cite this page
ScholarGate. (2026, June 1). Stochastic Block Model. ScholarGate. https://scholargate.app/network-analysis/stochastic-block-model