Bootstrap percolation on the stochastic block model with k communities

2018/12/21 by Giovanni Luca Torrisi, Torrisi, Giovanni Luca, Michele Garetto +3
Physics and Astronomy · Mathematics · #Complex Network Analysis Techniques #Opinion Dynamics and Social Influence #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.1812.09107

Abstract

We analyze the bootstrap percolation process on the stochastic block model (SBM), a natural extension of the Erdös--Rényi random graph that allows representing the "community structure" observed in many real systems. In the SBM, nodes are partitioned into subsets, which represent different communities, and pairs of nodes are independently connected with a probability that depends on the communities they belong to. Under mild assumptions on system parameters, we prove the existence of a sharp phase transition for the final number of active nodes and characterize sub-critical and super-critical regimes in terms of the number of initially active nodes, which are selected uniformly at random in each community.

Citations

• Bootstrap Percolation on a Graph with Random and Local Connections
• Large deviations for subcritical bootstrap percolation on the random graph

Related

• Bootstrap percolation on the stochastic block model
• Component structure and percolation in block models
• Bootstrap percolation on the random regular graph
• Algorithm independent bounds on community detection problems and\n associated transitions in stochastic block model graphs
• Clique percolation in random networks