Generalized nonbacktracking bounds on the influence in independent cascade models

Emmanuel Abbe, Sanjeev Kulkarni, Eun Jee Lee

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
JournalJournal of Machine Learning Research
StatePublished - Feb 1 2020

All Science Journal Classification (ASJC) codes

  • Software
  • Artificial Intelligence
  • Control and Systems Engineering
  • Statistics and Probability


  • Independent Cascade Model
  • Influence Estimation
  • Message Passing
  • Nonbacktracking Walk
  • Social Networks


Dive into the research topics of 'Generalized nonbacktracking bounds on the influence in independent cascade models'. Together they form a unique fingerprint.

Cite this