Generalized nonbacktracking bounds on the influence in independent cascade models

Emmanuel Abbe; Sanjeev Kulkarni; Eun Jee Lee

Generalized nonbacktracking bounds on the influence in independent cascade models

Emmanuel Abbe, Sanjeev Kulkarni, Eun Jee Lee

Research output: Contribution to journal › Article › peer-review

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 language	English (US)
Journal	Journal of Machine Learning Research
Volume	21
State	Published - Feb 1 2020

All Science Journal Classification (ASJC) codes

Software
Artificial Intelligence
Control and Systems Engineering
Statistics and Probability

Keywords

Independent Cascade Model
Influence Estimation
Message Passing
Nonbacktracking Walk
Social Networks

Cite this

@article{7d910a45fd3a4259b61e4fc60d47088b,

title = "Generalized nonbacktracking bounds on the influence in independent cascade models",

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.",

keywords = "Independent Cascade Model, Influence Estimation, Message Passing, Nonbacktracking Walk, Social Networks",

author = "Emmanuel Abbe and Sanjeev Kulkarni and Lee, {Eun Jee}",

note = "Publisher Copyright: {\textcopyright} 2020 Emmanuel Abbe, Sanjeev Kulkarni, Eun Jee Lee. License: CC-BY 4.0, see https://creativecommons.org/licenses/by/4.0/. Attribution requirements are provided at http://jmlr.org/papers/v21/18-112.html.",

year = "2020",

month = feb,

day = "1",

language = "English (US)",

volume = "21",

journal = "Journal of Machine Learning Research",

issn = "1532-4435",

publisher = "Microtome Publishing",

}

TY - JOUR

T1 - Generalized nonbacktracking bounds on the influence in independent cascade models

AU - Abbe, Emmanuel

AU - Kulkarni, Sanjeev

AU - Lee, Eun Jee

N1 - Publisher Copyright: © 2020 Emmanuel Abbe, Sanjeev Kulkarni, Eun Jee Lee. License: CC-BY 4.0, see https://creativecommons.org/licenses/by/4.0/. Attribution requirements are provided at http://jmlr.org/papers/v21/18-112.html.

PY - 2020/2/1

Y1 - 2020/2/1

N2 - 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.

AB - 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.

KW - Independent Cascade Model

KW - Influence Estimation

KW - Message Passing

KW - Nonbacktracking Walk

KW - Social Networks

UR - http://www.scopus.com/inward/record.url?scp=85086799918&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85086799918&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:85086799918

SN - 1532-4435

VL - 21

JO - Journal of Machine Learning Research

JF - Journal of Machine Learning Research

ER -

Generalized nonbacktracking bounds on the influence in independent cascade models

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Other files and links

Fingerprint

Cite this