Skip to main content

Generalized Nonbacktracking Bounds on the Influence in Independent Cascade Models

Author(s): Abbe, Emmanuel; Kulkarni, Sanjeev R; Lee, Eun Jee

To refer to this page use:
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.
Publication Date: 2020
Citation: Abbe, Emmanuel, Kulkarni, Sanjeev R, Lee, Eun Jee. (2020). Generalized Nonbacktracking Bounds on the Influence.. J. Mach. Learn. Res., 21 (31:1 - 31:1
Pages: 1112-1147
Type of Material: Journal Article
Journal/Proceeding Title: Journal of Machine Learning Research
Version: Final published version. This is an open access article.

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.