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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Abebe, R., Adamic, L., Kleinberg, J.: Mitigating overexposure in viral marketing (2018)
Bai, W., Iyer, R., Wei, K., Bilmes, J.: Algorithms for optimizing the ratio of submodular functions. In: ICML, pp. 2751–2759 (2016)
Buchbinder, N., Feldman, M., Naor, J., Schwartz, R.: Submodular maximization with cardinality constraints. In: SODA, pp. 1433–1452 (2014)
Chen, W., et al.: Influence maximization in social networks when negative opinions may emerge and propagate. In: SDM, pp. 379–390 (2011)
Goyal, A., Lu, W., Lakshmanan, L.V.S.: SIMPATH: an efficient algorithm for influence maximization under the linear threshold model. In: ICDM, pp. 211–220 (2011)
Gupta, S.: A conceptual framework that identifies antecedents and consequences of building socially responsible international brands. Thunderbird Int. Bus. Rev. 58(3), 225–237 (2016)
Gwadera, R., Loukides, G.: Cost-effective viral marketing in the latency aware independent cascade model. In: PAKDD, pp. 251–265 (2017)
Iyer, R., Bilmes, J.: Algorithms for approximate minimization of the difference between submodular functions, with applications. In: UAI, pp. 407–417 (2012)
Kempe, D., Kleinberg, J., Tardos, E.: Maximizing the spread of influence through a social network. In: KDD, pp. 137–146 (2003)
Khan, A., Zehnder, B., Kossmann, D.: Revenue maximization by viral marketing: a social network host’s perspective. In: ICDE, pp. 37–48 (2016)
Krause, A., Golovin, D.: Submodular function maximization. In: Tractability (2013)
Li, F., Li, C., Shan, M.: Labeled influence maximization in social networks for target marketing. In: PASSAT/SocialCom 2011, pp. 560–563 (2011)
Li, Y., Fan, J., Wang, Y., Tan, K.: Influence maximization on social graphs: a survey. TKDE 30(10), 1852–1872 (2018)
Loukides, G., Gwadera, R.: Preventing the diffusion of information to vulnerable users while preserving pagerank. Int. J. Data Sci. Anal. 5(1), 19–39 (2018)
Manning, C., Raghavan, P., Schütze, M.: Introduction to Information Retrieval (2008)
Mitrovic, M., Bun, M., Krause, A., Karbasi, A.: Differentially private submodular maximization: data summarization in disguise. In: ICML, pp. 2478–2487 (2017)
Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions. Math. Program. 14(1), 265–294 (1978)
Nielsen: Sustainable selections: how socially responsible companies are turning a profit. https://bit.ly/2DW99pE
Pasumarthi, R., Narayanam, R., Ravindran, B.: Near optimal strategies for targeted marketing in social networks. In: AAMAS, pp. 1679–1680 (2015)
Shaw, G., Karami, A.: Computational content analysis of negative tweets for obesity, diet, diabetes, and exercise. Proc. Assoc. Inf. Sci. Technol. 54(1), 357–365 (2017)
Song, C., Hsu, W., Lee, M.L.: Targeted influence maximization in social networks. In: CIKM, pp. 1683–1692 (2016)
Svitkina, Z., Fleischer, L.: Submodular approximation: sampling-based algorithms and lower bounds. SIAM J. Comput. 40(6), 1715–1737 (2011)
Wang, C., Chen, W., Wang, Y.: Scalable influence maximization for independent cascade model in large-scale social networks. DMKD 25(3), 545–576 (2012)
Wen, Y.T., Peng, W., Shuai, H.: Maximizing social influence on target users. In: PAKDD, pp. 701–712 (2018)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Chen, H., Loukides, G., Fan, J., Chan, H. (2020). Limiting the Influence to Vulnerable Users in Social Networks: A Ratio Perspective. In: Barolli, L., Takizawa, M., Xhafa, F., Enokido, T. (eds) Advanced Information Networking and Applications. AINA 2019. Advances in Intelligent Systems and Computing, vol 926. Springer, Cham. https://doi.org/10.1007/978-3-030-15032-7_93
Download citation
DOI: https://doi.org/10.1007/978-3-030-15032-7_93
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-15031-0
Online ISBN: 978-3-030-15032-7
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)