Rumor Blocking (RB) aims to identify a certain number of seed nodes that spread positive information to suppress the spread of rumor nodes in social networks. However, RB only considers the number of nodes to be protected but does not specifically consider protecting the susceptible group, which has a high probability of exposure to rumors. To fill this gap, in this paper, we propose a new notion of Truth Score (TS) that captures the degree of rumor mitigation for susceptible group. On this basis, we propose the Truth Score Maximization (TSM) problem, whose goal is to find a truth campaign seed set with budget k so as to maximize its TS. We prove that TSM is NP-hard and its objective function is monotonic but non-submodular. To solve the problem, we first derive submodular lower and upper bounding functions for our objective. Then, a general framework is proposed, which offers \((1 - 1/e - \epsilon )\) -approximation for maximizing the proposed bounding functions. Combining these two approximation algorithms, our final solution for TSM provides a data-dependent approximation guarantee. Finally, we conduct experiments on real-world social networks to demonstrate the efficiency and effectiveness of the proposed algorithm.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Mitigate the Damage of Rumor on Susceptible Group

  • Yao Tang,
  • Jinghao Wang,
  • Chen Chen,
  • Xiaoyang Wang,
  • Wenjie Zhang,
  • Ying Zhang

摘要

Rumor Blocking (RB) aims to identify a certain number of seed nodes that spread positive information to suppress the spread of rumor nodes in social networks. However, RB only considers the number of nodes to be protected but does not specifically consider protecting the susceptible group, which has a high probability of exposure to rumors. To fill this gap, in this paper, we propose a new notion of Truth Score (TS) that captures the degree of rumor mitigation for susceptible group. On this basis, we propose the Truth Score Maximization (TSM) problem, whose goal is to find a truth campaign seed set with budget k so as to maximize its TS. We prove that TSM is NP-hard and its objective function is monotonic but non-submodular. To solve the problem, we first derive submodular lower and upper bounding functions for our objective. Then, a general framework is proposed, which offers \((1 - 1/e - \epsilon )\) -approximation for maximizing the proposed bounding functions. Combining these two approximation algorithms, our final solution for TSM provides a data-dependent approximation guarantee. Finally, we conduct experiments on real-world social networks to demonstrate the efficiency and effectiveness of the proposed algorithm.