Generalized Threshold-Based Epidemics in Random Graphs: the Power of Extreme Values

Speaker : Emilio Leonardi
Politecnico di Torino
Date: 05/10/2016
Time: 2:00 pm - 3:00 pm
Location: LINCS Meeting Room 40


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 recentlyinvestigated also in the context of random graphs, where it can serve as a simplemodel for a wide variety of cascades, such as thespreading of ideas, trends, viral contents, etc. over large social networks.In particular, it has been shown that in $G(n,p)$ the final active setcan exhibit a phase transition for a sub-linear number of seeds.In this paper, we propose a unique framework to study similarsub-linear phase transitions for a much broader class of graph modelsand epidemic processes. Specifically, we consider i) a generalized versionof bootstrap percolation in $G(n,p)$ with random activation thresholdsand random node-to-node influences; ii) different random graph models,including graphs with given degree sequence and graphs withcommunity structure (block model). The common thread of our work is toshow the surprising sensitivity of the critical seed set sizeto extreme values of distributions, which makes some systems dramaticallyvulnerable to large-scale outbreaks. We validate our results running simulation onboth synthetic and real graphs.

Joint work with M. Garetto and G. Torrisi, appeared at ACM SIGMETRIC 2016.