Targeted Protection Maximization in Social Networks
- 26 September 2019
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Network Science and Engineering
- Vol. 7 (3) , 1645-1655
Abstract
Unlike the classical rumor blocking problem, we study how to protect the targeted users from being influenced by rumor, called targeted protection maximization (TPM). It aims to block the least edges such that the expected ratio of nodes in targeted set influenced by rumor is at most $\beta$ . Under the IC-model, the objective function of TPM is monotone non-decreasing, but not submodular and not supermodular, which makes it difficult for us to solve it by existing algorithms. In this paper, we propose two efficient techniques to solve TPM problem, called Greedy and General-TIM. The Greedy uses simple Hill-Climbing strategy, and get a theoretical bound, but the time complexity is hard to accept. The second algorithm, General-TIM, is formed by means of randomized sampling by Reverse Shortest Path (Random-RS-Path), which reduces the time consuming significantly. A precise approximation ratio cannot be promised in General-TIM, but in fact, it can get good results in reality. Considering the community structure in networks, both Greedy and General-TIM can be improved after removing unrelated communities. Finally, the effectiveness and efficiency of our algorithms is evaluated on several real datasets.
Keywords
Funding Information
- National Science Foundation (1747818)
This publication has 23 references indexed in Scilit:
- Influence Maximization in Near-Linear Time2015
- Maximizing Social Influence in Nearly Optimal Time2013
- Gelling, and melting, large graphs by edge manipulation2012
- Containment of misinformation spread in online social networks2012
- Influence Blocking Maximization in Social Networks under the Competitive Linear Threshold Model2012
- Scalable influence maximization for prevalent viral marketing in large-scale social networks2010
- Cost-effective outbreak detection in networks2007
- Maximizing the spread of influence through a social network2003
- Submodular set functions, matroids and the greedy algorithm: Tight worst-case bounds and some generalizations of the Rado-Edmonds theoremDiscrete Applied Mathematics, 1984
- An analysis of approximations for maximizing submodular set functions—IMathematical Programming, 1978