Tight Bounds for Influence in Diffusion Networks and Application to Bond Percolation and Epidemiology
In this paper, we derive theoretical bounds for the long-term influence of a node in an Independent Cascade Model (ICM). We relate these bounds to the spectral radius of a particular matrix and show that the behavior is sub-critical when this spectral radius is lower than 1. More specifically, we point out that, in general networks, the sub-critical regime behaves in O(sqrt(n)) where n is the size of the network, and that this upper bound is met for star-shaped networks. We apply our results to epidemiology and percolation on arbitrary networks, and derive a bound for the critical value beyond which a giant connected component arises. Finally, we show empirically the tightness of our bounds for a large family of networks.
Code (0)
등록된 구현이 없습니다.
Tasks
EpidemiologySimilar Papers 제목 키워드 기반
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…
EpidemiologyMarketingSpectral estimation of the percolation transition in clustered networks
There have been several spectral bounds for the percolation transition in networks, using spectrum of matrices associated with the network such as the adjacency matrix and the non-backtracking matrix. However they are fa…
ClusteringModel-Independent Price Bounds for Catastrophic Mortality Bonds
In this paper, we are concerned with the valuation of Catastrophic Mortality Bonds and, in particular, we examine the case of the Swiss Re Mortality Bond 2003 as a primary example of this class of assets. This bond was t…
modelNonbacktracking Bounds on the Influence in Independent Cascade Models
This paper develops upper and lower bounds on the influence measure in a network, more precisely, the expected number of nodes that a seed set can influence in the independent cascade model. In particular, our bounds exp…
Community DetectionOn PAC-Bayes Bounds for Deep Neural Networks using the Loss Curvature
We investigate whether it's possible to tighten PAC-Bayes bounds for deep neural networks by utilizing the Hessian of the training loss at the minimum. For the case of Gaussian priors and posteriors we introduce a Hessia…
Variational Inference