Abstract
Online social networks have become an effective and important social platform for communication, opinions exchange, and information sharing. However, they also make it possible for rapid and wide misinformation diffusion, which may lead to pernicious influences on individuals or society. Hence, it is extremely important and necessary to detect the misinformation propagation by placing monitors.
In this article, we first define a general misinformation-detection problem for the case where the knowledge about misinformation sources is lacking, and show its equivalence to the influence-maximization problem in the reverse graph. Furthermore, considering node vulnerability, we aim to detect the misinformation reaching to a specific user. Therefore, we study a τ-Monitor Placement problem for cases where partial knowledge of misinformation sources is available and prove its #P complexity. We formulate a corresponding integer program, tackle exponential constraints, and propose a Minimum Monitor Set Construction (MMSC) algorithm, in which the cut-set2 has been exploited in the estimation of reachability of node pairs. Moreover, we generalize the problem from a single target to multiple central nodes and propose another algorithm based on a Monte Carlo sampling technique. Extensive experiments on real-world networks show the effectiveness of proposed algorithms with respect to minimizing the number of monitors.
- Ceren Budak, Divyakant Agrawal, and Amr El Abbadi. 2011. Limiting the spread of misinformation in social networks. In WWW. 665--674. Google ScholarDigital Library
- Salvatore A. Catanese, Pasquale De Meo, Emilio Ferrara, Giacomo Fiumara, and Alessandro Provetti. 2011. Crawling Facebook for social network analysis purposes. In Proceedings of the International Conference on Web Intelligence, Mining and Semantics. ACM, 52. Google ScholarDigital Library
- Meeyoung Cha, Hamed Haddadi, Fabricio Benevenuto, and P. Krishna Gummadi. 2010. Measuring user influence in Twitter: The million follower fallacy. ICWSM 10, (2010), 10--17.Google Scholar
- Meeyoung Cha, Alan Mislove, and Krishna P. Gummadi. 2009. A measurement-driven analysis of information propagation in the Flickr social network. In WWW. 721--730. Google ScholarDigital Library
- Wei Chen, Yifei Yuan, and Li Zhang. 2010. Scalable influence maximization in social networks under the linear threshold model. In ICDM. 88--97. Google ScholarDigital Library
- Shin-Ming Cheng, Vasileios Karyotis, Pin-Yu Chen, Kwang-Cheng Chen, and Symeon Papavassiliou. 2013. Diffusion models for information dissemination dynamics in wireless complex communication networks. Journal of Complex Systems 2013 (2013), 972352.Google ScholarCross Ref
- Nicholas A. Christakis and James H. Fowler. 2010. Social network sensors for early detection of contagious outbreaks. PloS one 5, 9 (2010), e12948.Google ScholarCross Ref
- Pedro Domingos and Matt Richardson. 2001. Mining the network value of customers. In KDD. 57--66. Google ScholarDigital Library
- Lidan Fan, Zaixin Lu, Weili Wu, Bhavani Thuraisingham, Huan Ma, and Yuanjun Bi. 2013. Least cost rumor blocking in social networks. In Proceedings of the 2013 IEEE 33rd International Conference on Distributed Computiing Systems (ICDCS). IEEE, 540--549. Google ScholarDigital Library
- Amit Goyal, Francesco Bonchi, and Laks V. S. Lakshmanan. 2010. Learning influence probabilities in social networks. In Proceedings of the 3rd ACM International Conference on Web Search and Data Mining. ACM, 241--250. Google ScholarDigital Library
- Ramanthan Guha, Ravi Kumar, Prabhakar Raghavan, and Andrew Tomkins. 2004. Propagation of trust and distrust. In Proceedings of the 13th International Conference on World Wide Web. ACM, 403--412. Google ScholarDigital Library
- Adrien Guille, Hakim Hacid, Cécile Favre, and Djamel A. Zighed. 2013. Information diffusion in online social networks: A survey. ACM SIGMOD Record 42, 2 (2013), 17--28. Google ScholarDigital Library
- http://snap.stanford.edu/data. Stanford large network dataset collection.Google Scholar
- Amanda Lee Hughes and Leysia Palen. 2009. Twitter adoption and use in mass convergence and emergency events. International Journal of Emergency Management 6, 3 (2009), 248--260.Google ScholarCross Ref
- Jing Jiang, Christo Wilson, Xiao Wang, Wenpeng Sha, Peng Huang, Yafei Dai, and Ben Y Zhao. 2013. Understanding latent interactions in online social networks. ACM Transactions on the Web (TWEB) 7, 4 (2013), 18. Google ScholarDigital Library
- Fang Jin, Edward Dougherty, Parang Saraf, Yang Cao, and Naren Ramakrishnan. 2013. Epidemiological modeling of news and rumors on Twitter. In SNAKDD. 8. Google ScholarDigital Library
- D. Kempe, J. M. Kleinberg, and V. Tardos. 2003. Maximizing the spread of influence through a social network. In KDD. 137--146. Google ScholarDigital Library
- Andreas Krause and Carlos Guestrin. 2011. Submodularity and its applications in optimized information gathering. ACM Transactions on Intelligent Systems and Technology (TIST) 2, 4 (2011), 32. Google ScholarDigital Library
- Sejeong Kwon, Meeyoung Cha, Kyomin Jung, Wei Chen, and Yajun Wang. 2013. Prominent features of rumor propagation in online social media. In ICDM. 1103--1108.Google Scholar
- Kyumin Lee, James Caverlee, Krishna Y. Kamath, and Zhiyuan Cheng. 2012. Detecting collective attention spam. In Proceedings of the 2nd Joint WICOW/AIRWeb Workshop on Web Quality. ACM, 48--55. Google ScholarDigital Library
- Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne VanBriesen, and Natalie Glance. 2007. Cost-effective outbreak detection in networks. In KDD. 420--429. Google ScholarDigital Library
- Stephan Lewandowsky, Ullrich K. H. Ecker, Colleen M. Seifert, Norbert Schwarz, and John Cook. 2012. Misinformation and its correction: Continued influence and successful debiasing. Psychological Science in the Public Interest 13, 3 (2012), 106--131.Google ScholarCross Ref
- Shuyang Lin, Fengjiao Wang, Qingbo Hu, and Philip S. Yu. 2013. Extracting social events for learning better information diffusion models. In Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 365--373. Google ScholarDigital Library
- Wuqiong Luo, Wee Peng Tay, and Mei Leng. 2013. Identifying infection sources and regions in large networks. IEEE Transactions on Signal Processing 61, 11 (2013), 2850--2865. Google ScholarDigital Library
- Marcelo Mendoza, Barbara Poblete, and Carlos Castillo. 2010. Twitter under crisis: Can we trust what we RT? In SOMA. 71--79. Google ScholarDigital Library
- Pasquale de Meo, Emilio Ferrara, Fabian Abel, Lora Aroyo, and Geert-Jan Houben. 2013. Analyzing user behavior across social sharing environments. ACM Transactions on Intelligent Systems and Technology (TIST) 5, 1 (2013), 14. Google ScholarDigital Library
- Nam P. Nguyen, Guanhua Yan, My T. Thai, and Stephan Eidenbenz. 2012. Containment of misinformation spread in online social networks. In WebSci. 213--222. Google ScholarDigital Library
- N. Pathak, A. Banerjee, and J. Srivastava. 2010a. A generalized linear threshold model for multiple cascades. In ICDM. 965--970. Google ScholarDigital Library
- Nishith Pathak, Arindam Banerjee, and Jaideep Srivastava. 2010b. A generalized linear threshold model for multiple cascades. In Proceedings of the 2010 IEEE 10th International Conference on Data Mining (ICDM). IEEE, 965--970. Google ScholarDigital Library
- B. Aditya Prakash, Jilles Vreeken, and Christos Faloutsos. 2012. Spotting culprits in epidemics: How many and which ones? In ICDM, Vol. 12. 11--20. Google ScholarDigital Library
- Vahed Qazvinian, Emily Rosengren, Dragomir R. Radev, and Qiaozhu Mei. 2011. Rumor has it: Identifying misinformation in microblogs. In EMNLP. 1589--1599. Google ScholarDigital Library
- Jacob Ratkiewicz, Michael Conover, Mark Meiss, Bruno Gonçalves, Alessandro Flammini, and Filippo Menczer. 2011. Detecting and tracking political abuse in social media. In ICWSM.Google Scholar
- Manuel Gomez Rodriguez and Bernhard Schölkopf. 2012. Influence maximization in continuous time diffusion networks. In Proceedings of the 29th International Conference on Machine Learning (ICML). 313--320.Google Scholar
- Eunsoo Seo, Prasant Mohapatra, and Tarek Abdelzaher. 2012. Identifying rumors and their sources in social networks. In SPIE Defense, Security, and Sensing. International Society for Optics and Photonics, 83891I--83891I.Google Scholar
- Devavrat Shah and Tauhid Zaman. 2011. Rumors in a network: Who’s the culprit? Information Theory, IEEE Transactions on 57, 8 (2011), 5163--5181. Google ScholarDigital Library
- Rudra M. Tripathy, Amitabha Bagchi, and Sameep Mehta. 2010. A study of rumor control strategies on social networks. In Proceedings of the 19th ACM International Conference on Information and Knowledge Management. ACM, 1817--1820. Google ScholarDigital Library
- Rudra M. Tripathy, Amitabha Bagchi, and Sameep Mehta. 2013. Towards combating rumors in social networks: Models and metrics. Intelligent Data Analysis 17, 1 (2013), 149--175. Google ScholarDigital Library
- Leslie G. Valiant. 1979. The complexity of enumeration and reliability problems. SIAM J. Comput. 8, 3 (1979), 410--421.Google ScholarDigital Library
- Gadi Wolfsfeld, Elad Segev, and Tamir Sheafer. 2013. Social media and the Arab Spring: Politics comes first. The International Journal of Press/Politics 18, 2 (2013), 115--137.Google Scholar
- Maria S. Zaragoza, R. S. Belli, and Kristie E. Payment. 2006. Misinformation effects and the suggestibility of eyewitness memory. Do Justice and Let the Sky Fall: Elizabeth F. Loftus and her Contributions to Science, Law, and Academic Freedom (2006), 35--63.Google Scholar
- Zhao Zhang, Wen Xu, Weili Wu, and Ding-Zhu Du. 2015. A novel approach for detecting multiple rumor sources in networks with partial observations. Journal of Combinatorial Optimization (2015), 1--15.Google Scholar
- Kai Zhu and Lei Ying. 2014. A robust information source estimator with sparse observations. Computational Social Networks 1, 1 (2014), 1--21.Google ScholarCross Ref
Index Terms
Misinformation in Online Social Networks: Detect Them All with a Limited Budget
Recommendations
Containment of misinformation spread in online social networks
WebSci '12: Proceedings of the 4th Annual ACM Web Science ConferenceWith their blistering expansions in recent years, popular on-line social sites such as Twitter, Facebook and Bebo, have become some of the major news sources as well as the most effective channels for viral marketing nowadays. However, alongside these ...
Detecting misinformation in online social networks before it is too late
ASONAM '16: Proceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and MiningWhile online social networks provide access to a massive information source, they also enable wide dissemination of false or inaccurate content. Undesirable results caused by misinformation propagation make its timely detection very imperative. An ...
Analysis of misinformation containment in online social networks
With their blistering expansion in recent years, popular online social sites such as Twitter, Facebook and Bebo, have become not only one of the most effective channels for viral marketing but also the major news sources for many people nowadays. ...
Comments