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

Huiping Chen, Grigorios Loukides*, Solon P. Pissis, Hau Chan

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review


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.

Original languageEnglish
Pages (from-to)84-103
Number of pages20
JournalTheoretical Computer Science
Early online date20 Nov 2020
Publication statusPublished - 8 Jan 2021


  • Influence maximization
  • Social networks
  • Vulnerable nodes


Dive into the research topics of 'Influence maximization in the presence of vulnerable nodes: A ratio perspective'. Together they form a unique fingerprint.

Cite this