Generalized Nonbacktracking Bounds on the Influence
Emmanuel Abbe, Sanjeev Kulkarni, Eun Jee Lee; 21(31):1−36, 2020.
Abstract
This paper develops deterministic 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 r-nonbacktracking walks and Fortuin-Kasteleyn-Ginibre (FKG) type inequalities, and are computed by message passing algorithms. Further, we provide parameterized versions of the bounds that control the trade-off between efficiency and accuracy. Finally, the tightness of the bounds is illustrated on various network models.
[abs]
[pdf][bib]| © JMLR 2020. (edit, beta) |