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