Anytime Influence Bounds and the Explosive Behavior of Continuous-Time Diffusion Networks
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.
- It would to point out that p_ij(t) are actually subprobabilities, since \int_{0}^{\infty} p_{ij}(t) < 1.- Daneshmand et al. [ICML '14] also use the naming "hazard matrix" to denote a different quantity on a set of observed cascades. It would be useful to point out this, highlighting the differences.- In section 4.1., the authors do not explicitly state that \alpha_{ij} in [0, 1). I think this is necessary for p_{ij}(t) to be a (sub)probability.- The writing of the first paragraph of the introduction could be heavily improved.- The authors refer to [3] as early work on influence maximization. [3] does not tackle the influence maximization problem, but a different one.- The proof of Lemma 3 could be described more explicitly. In particular, explicitly relate f(x), g(x) and \mu(x) to the actual functions in the problem setting. This would help a reader to understand the definition of "right positive correlation", which is never formally written.- In Eq. (11) in the proof of Lemma 4, the authors should explicitly write what is a and x in ln(1 - ax) >= ln (1-a)x to help the reader.- In Eq. 12, should f_i(s) on the right side not be f_j(s)?- There is some very recent work that aims to establish the theoretical foundations of influence models. In particular, there are sample complexity results on the recovery of influence models:Daneshmand et al., ICML 2014 Pouget-Abadie et al., ICML 2015Although different to this work, it would help the reader understanding that there is already an on-going interest on the theoretical analysis of such models.