.png){kind=icon}
返回
An Efficient Randomized Algorithm for Rumor Blocking in Online Social Networks
.png){kind=icon}
OA
AI
DOI：10.1109/TNSE.2017.2783190.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Social networks allow rapid spread of ideas and innovations while negative information can also propagate widely. When a user receives two opposing opinions, they tend to believe the one arrives first. Therefore, once misinformation or rumor is detected, one containment method is to introduce a positive cascade competing against the rumor. Given a budget k, the rumor blocking problem asks for k seed users to trigger the spread of a positive cascade such that the number of the users who are not influenced by rumor can be maximized. The prior works have shown that the rumor blocking problem can be approximated within a factor of (1-1/e) by a classic greedy algorithm combined with Monte Carlo simulation. Unfortunately, the Monte Carlo simulation based methods are time consuming and the existing algorithms either trade performance guarantees for practical efficiency or vice versa. In this paper, we present a randomized approximation algorithm which is provably superior to the state-of-the art methods with respect to running time. The superiority of the proposed algorithm is demonstrated by experiments done on both the real-world and synthetic social networks.
Keyword:
Approximation algorithms
Social network services
Integrated circuit modeling
Monte Carlo methods
Linear programming
Algorithm design and analysis
Greedy algorithms
Social networks
rumor blocking
approximation algorithm
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
I
IF:
7.9
论文数:
2.6K
被引数:
10.0K
机构
引用论文
.png){kind=icon}
查看更多内容