Anytime Influence Bounds and the Explosive Behavior of Continuous-Time Diffusion Networks
Anytime Influence Bounds and the Explosive Behavior of Continuous-Time Diffusion Networks
复制标题
DOI：
--
复制
发表时间：
2015-12
期刊：
影响因子：
--
通讯作者：
Kevin Scaman;Rémi Lemonnier;N. Vayatis
中科院分区：
文献类型：
--
作者：
Kevin Scaman;Rémi Lemonnier;N. Vayatis
本文研究了沿着图上扩散过程中观测到的信息级联中的跃迁现象。我们介绍了拉普拉斯风险矩阵，并表明其光谱半径充分表征的影响和爆炸时间方面的传染病的动态。使用这个概念，我们证明了一组节点的影响紧的非渐近界，我们还提供了一个深入的分析，在此之后的传染成为超临界的临界时间。我们的贡献包括正式的定义和严格的下限临界爆炸时间。我们通过流行病学和病毒营销模型中使用的信息级联的几个例子来说明我们的理论结果的相关性。最后，我们为各种类型的网络提供了一系列的数值实验，证实了理论界的紧密性。
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.