Generalized nonbacktracking bounds on the influence in independent cascade models

Emmanuel Auguste Abbe, Sanjeev Kulkarni, Eun Jee Lee

Research output: Contribution to journalArticle

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.

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

All Science Journal Classification (ASJC) codes

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

Keywords

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

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

  • Cite this