2016/03/15 by Michele Garetto, Garetto, Michele, Emilio Leonardi +3
Mathematics · Physics and Astronomy · #Complex Network Analysis Techniques #FOS: Computer and information sciences #FOS: Physical sciences #Opinion Dynamics and Social Influence #Physics and Society (physics.soc-ph) #Social and Information Networks (cs.SI) #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.1603.04643
openalex publication_date 2016/03/15 · openalex created_date 2019/06/27 · openalex updated_date 2026/07/28
Bootstrap percolation is a well-known activation process in a graph, in which a node becomes active when it has at least r active neighbors. Such process, originally studied on regular structures, has been recently investigated also in the context of random graphs, where it can serve as a simple model for a wide variety of cascades, such as the spreading of ideas, trends, viral contents, etc. over large social networks. In particular, it has been shown that in G(n,p) the final active set can exhibit a phase transition for a sub-linear number of seeds. In this paper, we propose a unique framework to study similar sub-linear phase transitions for a much broader class of graph models and epidemic processes. Specifically, we consider i) a generalized version of bootstrap percolation in G(n,p) with random activation thresholds and random node-to-node influences; ii) different random graph models, including graphs with given degree sequence and graphs with community structure (block model). The common thread of our work is to show the surprising sensitivity of the critical seed set size to extreme values of distributions, which makes some systems dramatically vulnerable to large-scale outbreaks. We validate our results running simulation on both synthetic and real graphs.