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.
Code (0)
등록된 구현이 없습니다.
Tasks
EpidemiologyMarketingSimilar Papers 제목 키워드 기반
Dynamic Importance Sampling for Anytime Bounds of the Partition Function
Computing the partition function is a key inference task in many graphical models. In this paper, we propose a dynamic importance sampling scheme that provides anytime finite-sample bounds for the partition function. Ou…
Heuristic SearchBounded Optimal Exploration in MDP
Within the framework of probably approximately correct Markov decision processes (PAC-MDP), much theoretical work has focused on methods to attain near optimality after a relatively long period of learning and exploratio…
More PAC-Bayes bounds: From bounded losses, to losses with general tail behaviors, to anytime validity
In this paper, we present new high-probability PAC-Bayes bounds for different types of losses. Firstly, for losses with a bounded range, we recover a strengthened version of Catoni's bound that holds uniformly for all pa…
validActive Tuples-based Scheme for Bounding Posterior Beliefs
The paper presents a scheme for computing lower and upper bounds on the posterior marginals in Bayesian networks with discrete variables. Its power lies in its ability to use any available scheme that bounds the probabil…
Continuous Prediction with Experts' Advice
Prediction with experts' advice is one of the most fundamental problems in online learning and captures many of its technical challenges. A recent line of work has looked at online learning through the lens of differenti…
Prediction