Influence maximization in the presence of vulnerable nodes: A ratio perspective - Archive ouverte HAL Access content directly
Journal Articles Theoretical Computer Science Year : 2021

Influence maximization in the presence of vulnerable nodes: A ratio perspective

(1) , (1) , (2, 3) , (4)
1
2
3
4

Abstract

Influence maximization is a key problem seeking to identify users who will diffuse information to influence the largest number of other users in a social network. A drawback of the influence maximization problem is that it could be socially irresponsible to influence users many of whom would be harmed, due to their demographics, health conditions, or socioeconomic characteristics (e.g., predominantly overweight people influenced to buy junk food). Motivated by this drawback and by the fact that some of these vulnerable users will be influenced inadvertently, we introduce the problem of finding a set of users (seeds) that limits the influence to vulnerable users while maximizing the influence to the non-vulnerable users. We define a measure that captures the quality of a set of seeds as an additively smoothed ratio (ASR) between the expected number of influenced non-vulnerable users and the expected number of influenced vulnerable users. Then, we develop methods which aim to find a set of seeds that maximizes the measure: greedy heuristics, an approximation algorithm, as well as several variations of the approximation algorithm. We evaluate our methods on synthetic and real-world datasets and demonstrate they substantially outperform a state-of-the-art competitor in terms of both effectiveness and efficiency. We also demonstrate that the variations of our approximation algorithm offer different trade-offs between effectiveness and efficiency.
Fichier principal
Vignette du fichier
TCS_VM_final.pdf (1.14 Mo) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-03498444 , version 1 (21-12-2021)

Identifiers

Cite

Huiping Chen, Grigorios Loukides, Solon P Pissis, Hau Chan. Influence maximization in the presence of vulnerable nodes: A ratio perspective. Theoretical Computer Science, 2021, 852, pp.84-103. ⟨10.1016/j.tcs.2020.11.020⟩. ⟨hal-03498444⟩

Collections

INRIA INRIA2
9 View
39 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More