Targeted Protection Maximization in Social Networks

被引:26
作者
Guo, Jianxiong [1 ]
Li, Yi [2 ]
Wu, Weili [1 ]
机构
[1] Univ Texas Dallas, Dept Comp Sci, Erik Jonsson Sch Engn & Comp Sci, Richardson, TX 75080 USA
[2] Univ Texas Tyler, Dept Comp Sci, Soules Coll Business, Tyler, TX 75799 USA
来源
IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING | 2020年 / 7卷 / 03期
基金
美国国家科学基金会;
关键词
Targeted Protection Maximization; rumor blocking; social network; randomized algorithm; BLOCKING;
D O I
10.1109/TNSE.2019.2944108
中图分类号
T [工业技术];
学科分类号
08 ;
摘要
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 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.
引用
收藏
页码:1645 / 1655
页数:11
相关论文
共 31 条
[1]   Social Media and Fake News in the 2016 Election [J].
Allcott, Hunt ;
Gentzkow, Matthew .
JOURNAL OF ECONOMIC PERSPECTIVES, 2017, 31 (02) :211-235
[2]  
[Anonymous], 2014, Convex Optimiza- tion
[3]  
[Anonymous], 2012, P ACM INT C INF KNOW, DOI DOI 10.1145/2396761.2396795
[4]  
[Anonymous], 2003, P ACM SIGKDD
[5]  
Arazkhani N, 2019, 2019 5TH INTERNATIONAL CONFERENCE ON WEB RESEARCH (ICWR), P258, DOI [10.1109/icwr.2019.8765277, 10.1109/ICWR.2019.8765277]
[6]  
Bian Andrew An, 2017, Proceedings of the 34 th International Conference on Machine Learning, P498
[7]  
Borgs C, 2014, P 25 ANN ACM SIAM S, P946, DOI DOI 10.1137/1.9781611973402.70
[8]  
Budak C., 2011, P 20 INT C WORLD WID, P665, DOI DOI 10.1145/1963405.1963499
[9]  
Chen W, 2010, P 16 ACM SIGKDD INT, V10, P1029
[10]   SUBMODULAR SET-FUNCTIONS, MATROIDS AND THE GREEDY ALGORITHM - TIGHT WORST-CASE BOUNDS AND SOME GENERALIZATIONS OF THE RADO-EDMONDS THEOREM [J].
CONFORTI, M ;
CORNUEJOLS, G .
DISCRETE APPLIED MATHEMATICS, 1984, 7 (03) :251-274