Percolation transitions depend on evolving community structure in networks
Percolation in the Stochastic Block Model
Social and Information Networks
Summary
Networks often have groups or communities that change as the network grows. The authors studied how connections spread through these groups when the size and number of communities change over time. They found that the usual rule about when a big connected cluster forms (called the percolation threshold) does not always apply when communities evolve. Their new approach better predicts this threshold in more realistic network scenarios and shows when common methods may fail due to complex connection patterns.
What this means in practice
- •For network engineers: Predict connectivity thresholds in evolving communication networks with changing community groups to optimize reliability.
- •For social media platform developers: Model how information spreads when user communities shift over time, improving recommendation and moderation tools.
Authors
Luca Pieleanu, Moritz Laber, Narayan G. Sabhahit, Dmitri Krioukov
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.