Nonbacktracking Bounds on the Influence in Independent Cascade Models
Abstract
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 exploit nonbacktracking walks, Fortuin-Kasteleyn-Ginibre type inequalities, and are computed by message passing algorithms. Nonbacktracking walks have recently allowed for headways in community detection, and this paper shows that their use can also impact the influence computation. Further, we provide parameterized versions of the bounds that control the trade-off between the efficiency and the accuracy. Finally, the tightness of the bounds is illustrated with simulations on various network models.
Cite
Text
Abbe et al. "Nonbacktracking Bounds on the Influence in Independent Cascade Models." Neural Information Processing Systems, 2017.Markdown
[Abbe et al. "Nonbacktracking Bounds on the Influence in Independent Cascade Models." Neural Information Processing Systems, 2017.](https://mlanthology.org/neurips/2017/abbe2017neurips-nonbacktracking/)BibTeX
@inproceedings{abbe2017neurips-nonbacktracking,
title = {{Nonbacktracking Bounds on the Influence in Independent Cascade Models}},
author = {Abbe, Emmanuel and Kulkarni, Sanjeev and Lee, Eun Jee},
booktitle = {Neural Information Processing Systems},
year = {2017},
pages = {1407-1416},
url = {https://mlanthology.org/neurips/2017/abbe2017neurips-nonbacktracking/}
}