Limiting the Influence to Vulnerable Users in Social Networks: A Ratio Perspective

Abstract

Influence maximization is a key problem in social networks, seeking to find users who will diffuse information to influence a large number of users. A drawback of the standard influence maximization is that it is unethical 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 between the expected number of influenced non-vulnerable users and the expected number of influenced vulnerable users. Then, we develop greedy heuristics and an approximation algorithm called ISS for our problem, which aim to find a set of seeds that maximizes the measure. We evaluate our methods on synthetic and real-world datasets and demonstrate that ISS substantially outperforms a heuristic competitor in terms of both effectiveness and efficiency while being more effective and/or efficient than the greedy heuristics.