%0 Journal Article
%T Tight Bounds for Influence in Diffusion Networks and Application to Bond Percolation and Epidemiology
%A Remi Lemonnier
%A Kevin Scaman
%A Nicolas Vayatis
%J Computer Science
%D 2014
%I arXiv
%X 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.
%U http://arxiv.org/abs/1407.4744v1