Percolation in Random Graphs of Unbounded Rank

Bootstrap percolation in (random) graphs is a contagion dynamics 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 neighbor...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2022-11
Main Authors: Detering, Nils, Lin, Jimin
Format: Article
Language:English
Subjects:
Algorithms
Apexes
Clustering
Function space
Graphs
Linear operators
Neural networks
Operators (mathematics)
Percolation
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Bootstrap percolation in (random) graphs is a contagion dynamics 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 exceeds \(k\). This process has been studied extensively in so called \textit{rank one} models. These models can generate random graphs with heavy-tailed degree sequences but they are not capable of clustering. In this paper, we treat a class of random graphs of unbounded rank which allow for extensive clustering. Our main result determines the final fraction of infected vertices as the fixed point of a non-linear operator defined on a suitable function space. We propose an algorithm that facilitates neural networks to calculate this fixed point efficiently. We further derive criteria based on the Fréchet derivative of the operator that allows one to determine whether small infections spread through the entire graph or rather stay local.
ISSN:2331-8422