The paper studies transition phenomena in information cascades observed along a diffusion process over some graph. We introduce the Laplace Hazard matrix and show that its spectral radius fully characterizes the dynamics of the contagion both in terms of influence and of explosion time. Using this concept, we prove tight non-asymptotic bounds for the influence of a set of nodes, and we also provide an in-depth analysis of the critical time after which the contagion becomes super-critical. Our contributions include formal definitions and tight lower bounds of critical explosion time. We illustrate the relevance of our theoretical results through several examples of information cascades used in epidemiology and viral marketing models. Finally, we provide a series of numerical experiments for various types of networks which confirm the tightness of the theoretical bounds.
Kevin Scaman (ENS Cachan - CMLA)
Rémi Lemonnier (ENS Cachan - CMLA)
Nicolas Vayatis (ENS Cachan - CMLA)
More from the Same Authors
2014 Poster: Tight Bounds for Influence in Diffusion Networks and Application to Bond Percolation and Epidemiology »
Remi Lemonnier · Kevin Scaman · Nicolas Vayatis