Percolation in the Stochastic Block Model
Abstract
The stochastic block model is a paradigmatic model of networks with community structure. Yet percolation in the model has been studied primarily in cases with a fixed block structure, even though in real networks, the community structure may evolve as the network grows. Here we study percolation in sequences of stochastic block models in which the numbers and sizes of communities, as well as the intra- and intercommunity connection probabilities may all change with the network size. We analyze five such sequences using two methods: linearized self-consistent equations for the locally tree-like models and a branching process at the community scale for the models with nonvanishing clustering. We find that the critical average degree is not generally equal to $1$, even in locally tree-like sequences, because the transition depends on how connections are distributed across the evolving community structure. We also show that the community-scale branching process accurately predicts the transition when intercommunity connections are sufficiently sparse, even in the presence of nonvanishing clustering, while a geometric stochastic block model sequence demonstrates the limitations of this method when correlations between intercommunity connections cannot be neglected. These results extend percolation studies in the stochastic block model to more realistic scenarios with evolving community structure, and may provide new methods to derive the upper and lower bounds for the percolation threshold in geometric long-range percolation.
Related
- Stochastic dynamics generation of directed percolation using a two-channel convolutional neural network
- A Threshold Constant for Exact Community Recovery in the Degree-Corrected Poisson Stochastic Block Model
- Poisson Autoregression on a Large Network with a Stochastic Block Model Structure
- Limits of Stochastic Semigroups and Block-Triangular Majorisation
- Optimal Community Recovery by Spectrally Initialized Variational EM in General Stochastic Block Models
BibTeX
@misc{pieleanu2026percolation,
title = {{Percolation in the Stochastic Block Model}},
author = {Luca Pieleanu and Moritz Laber and Narayan G. Sabhahit and Dmitri Krioukov},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.27141},
eprint = {2609.27141},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.27141},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Percolation in the Stochastic Block Model
AU - Luca Pieleanu
AU - Moritz Laber
AU - Narayan G. Sabhahit
AU - Dmitri Krioukov
PY - 2026
DA - 2026/10/20
PB - arXiv
DO - 10.48550/arxiv.2609.27141
UR - https://arxiv.org/abs/2609.27141
AB - The stochastic block model is a paradigmatic model of networks with community structure. Yet percolation in the model has been studied primarily in cases with a fixed block structure, even though in real networks, the community structure may evolve as the network grows. Here we study percolation in sequences of stochastic block models in which the numbers and sizes of communities, as well as the intra- and intercommunity connection probabilities may all change with the network size. We analyze five such sequences using two methods: linearized self-consistent equations for the locally tree-like models and a branching process at the community scale for the models with nonvanishing clustering. We find that the critical average degree is not generally equal to $1$, even in locally tree-like sequences, because the transition depends on how connections are distributed across the evolving community structure. We also show that the community-scale branching process accurately predicts the transition when intercommunity connections are sufficiently sparse, even in the presence of nonvanishing clustering, while a geometric stochastic block model sequence demonstrates the limitations of this method when correlations between intercommunity connections cannot be neglected. These results extend percolation studies in the stochastic block model to more realistic scenarios with evolving community structure, and may provide new methods to derive the upper and lower bounds for the percolation threshold in geometric long-range percolation.
ER -