Paper Info
Title
Targeted Protection Maximization in Social Networks
Abstract
Even though the widespread use of social platforms provides convenience to our daily life, it causes some bad results at the same time. For example, misinformation and personal attack can be spread easily on social networks, which drives us to study how to block the spread of misinformation effectively. 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 b. 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.
Year
DOI
Venue
2020
10.1109/TNSE.2019.2944108
IEEE Transactions on Network Science and Engineering
Keywords
DocType
Volume
Targeted Protection Maximization,rumor blocking,social network,randomized algorithm
Journal
7
Issue
ISSN
Citations 
3
2327-4697
3
PageRank 
References 
Authors
0.37
0
3
Name
Order
Citations
PageRank
Jianxiong Guo1208.38
Yi Li212722.03
Weili Wu32093170.29