Robust rumor blocking problem with uncertain rumor sources in social networks
- PDF / 1,356,940 Bytes
- 19 Pages / 439.642 x 666.49 pts Page_size
- 86 Downloads / 180 Views
Robust rumor blocking problem with uncertain rumor sources in social networks Jianming Zhu1
· Smita Ghosh2 · Weili Wu2
Received: 2 June 2019 / Revised: 13 May 2020 / Accepted: 10 September 2020 / © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Rumormongers spread negative information throughout the social network, which may even lead to panic or unrest. Rumor should be blocked by spreading positive information from several protector nodes in the network. Users will not be influenced if they receive the positive information ahead of negative one. In many cases, network manager or government may not know the exact positions where rumor will start. Meanwhile, protector nodes also need to be selected in order to prepare for rumor blocking. Given a social network G = (V , E, P ), where P is the weight function on edge set E, P(u,v) is the probability that v is activated by u after u is activated. Assume there will be l rumormongers in the network while the exact positions are not clear, Robust Rumor Blocking(RRB) problem is to select k nodes as protector such that the expected eventually influenced users by rumor is minimized. RRB will be proved to be NP-hard and the objective function is neither submodular nor supermodular. We present an estimation process for the objective function of RRB based on Reverse Reachable Set(RR-Set) methods. A randomized greedy algorithm is designed for solving this problem. And this algorithm is proved to have approximation ratio α1 (1 − e−αγ )(1 + ) plus a constant, where γ is submodularity ratio and α is curvature.Finally, we evaluate our algorithm on real world data sets and do comparison among different strategies for protector. The results show the effectiveness and the efficiency of the proposed algorithm. Keywords Rumor blocking · Robust · Uncertainty · Reverse reachable set · Social network
Jianming Zhu
[email protected] Smita Ghosh [email protected] Weili Wu [email protected] 1
School of Engineering Science, University of Chinese Academy of Sciences, 19A Yuquan Rd., Beijing, China
2
Department of Computer Science, University of Texas at Dallas, Richardson, TX, USA
World Wide Web
1 Introduction With the soaring popularity of online social networks, such as Twitter, Facebook, Wechat and Chinese Sina Weibo, etc., more and more people are able to become friends and share all kinds of information with each other. These information contain positive and negative. Sometimes the negative information may turn out to be rumor. For example, in 2011 Japan Fukushima Daiichi nuclear-power was damaged by earthquake, consumers in cities along the China coastline, such as Shanghai and Guangzhou, and even in inland capital Beijing, began stockpiling table salt after problems while there were rumors that radiation would spread to China by air and sea and iodized table salt could protect body from radiation [7]. Salt was temporarily out of stock and salt price was 10 times over the usual price in some places. Another example is spread of misinforma
Data Loading...
