Home Page

Papers

Submissions

News

Editorial Board

Announcements

Proceedings

Open Source Software

Search

Statistics

Login

Frequenty Asked Questions

Contact Us



RSS Feed

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)