Bootstrap percolation in random graphs of unbounded rank

Abstract Bootstrap percolation in (random) graphs is a contagion dynamic among a set of vertices with certain threshold levels. The process is started by a set of initially infected vertices, and an initially uninfected vertex with threshold k gets infected as soon as the number of its infected neighbors reaches k . This process has been studied extensively in rank 1 models. These models can generate random graphs with heavy-tailed degree sequences but they are not capable of generating networks with a flexible stochastic block structure. In this paper, we treat a class of random graphs of unbounded rank that can generate flexible stochastic block structures. Our main result determines the limit in probability of the final fraction of infected vertices from the fixed point of a non-linear operator defined on a suitable function space. We propose a neural-network-based algorithm to calculate this fixed point efficiently. We further derive criteria based on the Fréchet derivative of the operator that allow it to be determined whether small infections spread through the entire graph or rather stay local.