Nonbacktracking Bounds on the Influence in Independent Cascade Models
This paper develops 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 nonbacktracking walks, Fortuin-Kasteleyn-Ginibre (FKG) type inequalities, and are computed by message passing implementation. Nonbacktracking walks have recently allowed for headways in community detection, and this paper shows that their use can also impact the influence computation. Further, we provide a knob to control the trade-off between the efficiency and the accuracy of the bounds. Finally, the tightness of the bounds is illustrated with simulations on various network models.
Code (0)
등록된 구현이 없습니다.
Tasks
Community DetectionSimilar Papers 제목 키워드 기반
Computing and maximizing influence in linear threshold and triggering models
We establish upper and lower bounds for the influence of a set of nodes in certain types of contagion models. We derive two sets of bounds, the first designed for linear threshold models, and the second more broadly appl…
Better Bounds on the Adaptivity Gap of Influence Maximization under Full-adoption Feedback
In the influence maximization (IM) problem, we are given a social network and a budget $k$, and we look for a set of $k$ nodes in the network, called seeds, that maximize the expected number of nodes that are reached by …
Online Influence Maximization under Independent Cascade Model with Semi-Bandit Feedback
We study the online influence maximization problem in social networks under the independent cascade model. Specifically, we aim to learn the set of "best influencers" in a social network online while repeatedly interacti…
Tight Bounds for Influence in Diffusion Networks and Application to Bond Percolation and Epidemiology
In this paper, we derive theoretical bounds for the long-term influence of a node in an Independent Cascade Model (ICM). We relate these bounds to the spectral radius of a particular matrix and show that the behavior is …
EpidemiologyAnytime Influence Bounds and the Explosive Behavior of Continuous-Time Diffusion Networks
The paper studies transition phenomena in information cascades observed along a diffusion process over some graph. We introduce the Laplace Hazard matrix and show that its spectral radius fully characterizes the dynamics…
EpidemiologyMarketing