期刊
IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING
卷 7, 期 3, 页码 1067-1078出版社
IEEE COMPUTER SOC
DOI: 10.1109/TNSE.2019.2903272
关键词
Social networking (online); Heuristic algorithms; Integrated circuit modeling; Greedy algorithms; Approximation algorithms; Dynamic programming; Social network; rumor blocking; submodularity; greedy algorithm; dynamic programming
资金
- National Natural Science Foundation of China [11671400, 61672524]
- National Science Foundation [1747818]
Online social networks, such as Facebook, Twitter, and Wechat have become major social tools. The users can not only keep in touch with family and friends, but also send and share the instant information. However, in some practical scenarios, we need to take effective measures to control the negative information spreading, e.g., rumors spread over the networks. In this paper, we first propose the minimizing influence of rumors (MIR) problem, i.e., selecting a blocker set B with k nodes such that the users' total activation probability by rumor source set S is minimized. Then, we employ the classical independent cascade (IC) model as an information diffusion model. Based on the IC model, we prove that the objective function is monotone decreasing and non-submodular. To address the MIR problem effectively, we propose a two-stages method generating candidate set and selecting blockers for the general networks. Furthermore, we also study the MIR problem on the tree network and propose a dynamic programming guaranteeing the optimal solution. Finally, we evaluate proposed algorithms by simulations on synthetic and real-life social networks, respectively. Experimental results show our algorithms are superior to the comparative heuristic approaches, such as out-degree, betweenness centrality, and PageRank.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据