https://hal-amu.archives-ouvertes.fr/hal-02373686Yang, WenjingWenjingYangMOFED - Modèles et Formalismes à Evénements Discrets - LIS - Laboratoire d'Informatique et Systèmes - AMU - Aix Marseille Université - UTLN - Université de Toulon - CNRS - Centre National de la Recherche ScientifiqueBrenner, LeonardoLeonardoBrennerMOFED - Modèles et Formalismes à Evénements Discrets - LIS - Laboratoire d'Informatique et Systèmes - AMU - Aix Marseille Université - UTLN - Université de Toulon - CNRS - Centre National de la Recherche ScientifiqueGiua, AlessandroAlessandroGiuaDIEE - Department of Electrical and Electronic Engineering [University of Cagliari] - University of CagliariInfluence Maximization in Independent Cascade Networks Based on Activation Probability ComputationHAL CCSD2019[INFO.INFO-AU] Computer Science [cs]/Automatic Control Engineering[INFO.INFO-SI] Computer Science [cs]/Social and Information Networks [cs.SI]Brenner, Leonardo2022-03-15 09:26:382022-04-29 08:38:502022-04-29 08:38:45enJournal articleshttps://hal-amu.archives-ouvertes.fr/hal-02373686/document10.1109/ACCESS.2019.2894073application/pdf1Based 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. First, we propose the path method that computes the exact value of the activation probabilities but has high complexity. Second, an approximated method, called SSS-Noself, is obtained by the modification of the existing SteadyStateSpread algorithm, based on fixed-point computation, to achieve better accuracy. Finally, an efficient approach, also based on fixed-point computation, is proposed to compute the probability that a node is activated through a path of minimal length from the seed set. This algorithm, called SSS-Bounded-Path algorithm, can provide a lower bound for the computation of activation probabilities. Furthermore, these proposed approaches are applied to the influence maximization problem combined with the SelectTopK algorithm, the RankedReplace algorithm, and the greedy algorithm.