Tight Bounds for Influence in Diffusion Networks and Application to Bond Percolation and Epidemiology
Abstract
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.
Cite
Text
Lemonnier et al. "Tight Bounds for Influence in Diffusion Networks and Application to Bond Percolation and Epidemiology." Neural Information Processing Systems, 2014.Markdown
[Lemonnier et al. "Tight Bounds for Influence in Diffusion Networks and Application to Bond Percolation and Epidemiology." Neural Information Processing Systems, 2014.](https://mlanthology.org/neurips/2014/lemonnier2014neurips-tight/)BibTeX
@inproceedings{lemonnier2014neurips-tight,
title = {{Tight Bounds for Influence in Diffusion Networks and Application to Bond Percolation and Epidemiology}},
author = {Lemonnier, Remi and Scaman, Kevin and Vayatis, Nicolas},
booktitle = {Neural Information Processing Systems},
year = {2014},
pages = {846-854},
url = {https://mlanthology.org/neurips/2014/lemonnier2014neurips-tight/}
}