Based on the concepts of word-of-mouth effect and viral marketing, the diffusion of an innovation may be triggered starting from a set of initial users. Estimating the influence spread is a preliminary step to determine a suitable or even optimal set of initial users to reach a given goal. In this paper, we focus on a stochastic model called the Independent Cascade model, and compare a few approaches to compute activation probabilities of nodes in a social network, i.e., the probability that a user adopts the innovation. In the paper, first we propose the Path Method which computes the exact value of the activation probabilities but it has high complexity. Second an approximated method, called SSS-Noself, is obtained by modification of the existing SteadyStateSpread algorithm, based on fixed-point computation, to achieve a better accuracy. Finally an efficient approach, also based on fixed-point computation, is proposed to compute the probability that a node is activated though a path of minimal length from the seed set. This algorithm, called SSS-Bound-T algorithm, can provide a lower-bound for the computation of activation probabilities.

Computation of Activation Probabilities in the Independent Cascade Model

Giua, Alessandro
Ultimo
2018-01-01

Abstract

Based on the concepts of word-of-mouth effect and viral marketing, the diffusion of an innovation may be triggered starting from a set of initial users. Estimating the influence spread is a preliminary step to determine a suitable or even optimal set of initial users to reach a given goal. In this paper, we focus on a stochastic model called the Independent Cascade model, and compare a few approaches to compute activation probabilities of nodes in a social network, i.e., the probability that a user adopts the innovation. In the paper, first we propose the Path Method which computes the exact value of the activation probabilities but it has high complexity. Second an approximated method, called SSS-Noself, is obtained by modification of the existing SteadyStateSpread algorithm, based on fixed-point computation, to achieve a better accuracy. Finally an efficient approach, also based on fixed-point computation, is proposed to compute the probability that a node is activated though a path of minimal length from the seed set. This algorithm, called SSS-Bound-T algorithm, can provide a lower-bound for the computation of activation probabilities.
2018
9781538650653
Computer Networks and Communications; Decision Sciences (miscellaneous); Control and Optimization; Hardware and Architecture; Information Systems; Control and Systems Engineering
File in questo prodotto:
File Dimensione Formato  
18codit_a.pdf

Solo gestori archivio

Descrizione: Articolo principale
Tipologia: versione editoriale (VoR)
Dimensione 813.28 kB
Formato Adobe PDF
813.28 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11584/250438
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 2
social impact