DataTerminology.comNEW
Also known as: SBM
A probabilistic graph model that partitions nodes into communities with block-specific edge probabilities to capture community structure.
DESCRIPTION
The Stochastic Block Model is a generative model for random graphs that encodes community structure by assigning nodes to blocks and parameterizing inter- and intra-block connection probabilities. It serves as a foundational model for community detection, benchmarking, and statistical inference in networks. Variants such as degree-corrected and mixed-membership SBMs address heterogeneity and overlapping communities. Estimation often uses maximum likelihood, Bayesian inference, or spectral methods. SBM underpins evaluations for clustering algorithms and graph embeddings, aiding model selection and hypothesis testing in network science.
ALTERNATIVE DEFINITIONS
Network Science (Barabási)
The stochastic block model (SBM) is a generative model for networks with community structure, in which nodes are partitioned into blocks and edges are placed between node pairs with probabilities that depend only on their block memberships.
Emphasizes generative nature and block-dependent edge probabilities as the essence of community structure.
University of Oxford
In the stochastic block model, vertices are assigned to communities and the probability of an edge between two vertices depends only on the communities to which they belong.
Highlights the conditional independence and community-based probability structure in SBM.
Stanford University
Stochastic Block Models generate graphs with community structure by assigning nodes to blocks and sampling edges according to a block-block probability matrix.
Introduces the block-block probability matrix as a compact parameterization.
RELATED TERMS
Community Detection Graph Clustering Degree-Corrected SBM Mixed-Membership SBM Configuration Model Modularity Spectral Clustering Louvain Algorithm Graph Neural Network
COMPETING TERMS
Erdős–Rényi Model Preferential Attachment Model
RELATIONS
- Broader: Model
KNOWLEDGE AREAS
Mathematics AI Data Science Semantic & Knowledge Modeling
TARGET AUDIENCE
Data Scientist AI Engineer Data Modeler Data Architect
EXTERNAL SOURCES
- Wikipedia - Stochastic block model
- arXiv - Mixed-membership SBM paper
- Network Science (Barabási) - Textbook section on SBM
- graph-tool - Bayesian SBM inference docs
TOP QUESTIONS
What is the core idea of the Stochastic Block Model?
SBM assumes nodes belong to latent communities and edges occur with probabilities determined by community pairs. This captures assortative or disassortative patterns typical in real networks.
Category: Definition
How is the Stochastic Block Model used in community detection?
SBM provides a statistical framework to infer communities via maximum likelihood or Bayesian methods, often outperforming heuristic modularity-based approaches on noisy graphs.
Category: Application
What is the difference between SBM and Degree-Corrected SBM?
Degree-Corrected SBM introduces node-specific parameters to model degree heterogeneity while preserving block structure, improving fit for networks with heavy-tailed degree distributions.
Category: Distinction
How does the Stochastic Block Model compare to the Erdős–Rényi Model?
Unlike Erdős–Rényi’s uniform edge probability, SBM uses block-specific probabilities, enabling structured communities rather than purely random connectivity.
Category: Alternatives
What are common pitfalls when fitting a Stochastic Block Model?
Overfitting with too many blocks, ignoring degree heterogeneity, and assuming disjoint communities in overlapping structures can mislead inference and reduce generalization.
Category: Mistakes
How do you choose the number of communities in SBM?
Use model selection via BIC/AIC, Bayesian nonparametrics, or description length criteria. Cross-validation and stability analysis can validate the chosen block count.
Category: Requirements
Is the Stochastic Block Model suitable for dynamic networks?
Extensions exist for temporal SBMs where block memberships or probabilities evolve over time, enabling time-aware community inference.
Category: Topic
What algorithms are typically used to estimate SBM parameters?
Expectation-Maximization, variational inference, Gibbs sampling, and spectral clustering are common approaches, depending on assumptions and scale.
Category: Methods
Where should I start learning about the Stochastic Block Model?
Barabási’s Network Science book, Stanford’s CS224W materials, and graph-tool’s Bayesian inference documentation offer practical and theoretical foundations.
Category: Learning