King's College London

TY - JOUR

T1 - Influence maximization in the presence of vulnerable nodes

T2 - A ratio perspective

AU - Chen, Huiping

AU - Loukides, Grigorios

AU - Pissis, Solon P.

AU - Chan, Hau

PY - 2021/1/8

Y1 - 2021/1/8

N2 - 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.

AB - 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.

KW - Influence maximization

KW - Social networks

KW - Vulnerable nodes

UR - http://www.scopus.com/inward/record.url?scp=85097068371&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2020.11.020

DO - 10.1016/j.tcs.2020.11.020

M3 - Article

AN - SCOPUS:85097068371

VL - 852

SP - 84

EP - 103

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -