Targeted Protection Maximization in Social Networks
Targeted Protection Maximization in Social Networks
复制标题
DOI：
10.1109/tnse.2019.2944108
复制
发表时间：
2020-07-01
影响因子：
6.6
通讯作者：
Wu, Weili
中科院分区：
文献类型：
--
作者：
Guo, Jianxiong;Li, Yi;Wu, Weili
尽管社交平台的广泛使用为我们的日常生活提供了便利，但同时也带来了一些不良后果。例如，错误信息和人身攻击可以在社交网络上轻松传播，这促使我们研究如何有效地阻止错误信息的传播。与经典的谣言拦截问题不同，我们研究了如何保护目标用户不受谣言的影响，称为目标保护最大化（TPM）。它的目标是阻塞最少的边，使得目标集中受谣言影响的节点的期望比率至多为beta。在IC模型下，TPM的目标函数是单调非减的，但不是子模的，也不是超模的，这使得我们很难用现有的算法来求解。在本文中，我们提出了两个有效的技术来解决TPM问题，称为贪婪和通用TIM。贪婪算法采用简单的爬山策略，得到了一个理论界，但时间复杂度难以接受。第二种算法，通用TIM，通过反向最短路径（Random-RS-Path）的随机采样，这大大减少了时间消耗。广义TIM不能保证精确的逼近比，但在实际应用中可以得到很好的结果。考虑到网络中的社团结构，删除不相关社团后，贪婪算法和广义TIM算法都得到了改进。最后，我们的算法的有效性和效率进行了评估在几个真实的数据集。
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.