skip to main content
research-article

Misinformation in Online Social Networks: Detect Them All with a Limited Budget

Authors Info & Claims
Published:11 April 2016Publication History
Skip Abstract Section

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.

References

  1. Ceren Budak, Divyakant Agrawal, and Amr El Abbadi. 2011. Limiting the spread of misinformation in social networks. In WWW. 665--674. Google ScholarGoogle ScholarDigital LibraryDigital Library
  2. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  3. 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 ScholarGoogle Scholar
  4. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  5. Wei Chen, Yifei Yuan, and Li Zhang. 2010. Scalable influence maximization in social networks under the linear threshold model. In ICDM. 88--97. Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. 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 ScholarGoogle ScholarCross RefCross Ref
  7. Nicholas A. Christakis and James H. Fowler. 2010. Social network sensors for early detection of contagious outbreaks. PloS one 5, 9 (2010), e12948.Google ScholarGoogle ScholarCross RefCross Ref
  8. Pedro Domingos and Matt Richardson. 2001. Mining the network value of customers. In KDD. 57--66. Google ScholarGoogle ScholarDigital LibraryDigital Library
  9. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  10. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  11. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  12. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  13. http://snap.stanford.edu/data. Stanford large network dataset collection.Google ScholarGoogle Scholar
  14. 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 ScholarGoogle ScholarCross RefCross Ref
  15. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  16. Fang Jin, Edward Dougherty, Parang Saraf, Yang Cao, and Naren Ramakrishnan. 2013. Epidemiological modeling of news and rumors on Twitter. In SNAKDD. 8. Google ScholarGoogle ScholarDigital LibraryDigital Library
  17. D. Kempe, J. M. Kleinberg, and V. Tardos. 2003. Maximizing the spread of influence through a social network. In KDD. 137--146. Google ScholarGoogle ScholarDigital LibraryDigital Library
  18. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  19. 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 ScholarGoogle Scholar
  20. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  21. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  22. 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 ScholarGoogle ScholarCross RefCross Ref
  23. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  24. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  25. Marcelo Mendoza, Barbara Poblete, and Carlos Castillo. 2010. Twitter under crisis: Can we trust what we RT? In SOMA. 71--79. Google ScholarGoogle ScholarDigital LibraryDigital Library
  26. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  27. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  28. N. Pathak, A. Banerjee, and J. Srivastava. 2010a. A generalized linear threshold model for multiple cascades. In ICDM. 965--970. Google ScholarGoogle ScholarDigital LibraryDigital Library
  29. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  30. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  31. Vahed Qazvinian, Emily Rosengren, Dragomir R. Radev, and Qiaozhu Mei. 2011. Rumor has it: Identifying misinformation in microblogs. In EMNLP. 1589--1599. Google ScholarGoogle ScholarDigital LibraryDigital Library
  32. 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 ScholarGoogle Scholar
  33. 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 ScholarGoogle Scholar
  34. 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 ScholarGoogle Scholar
  35. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  36. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  37. 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 ScholarGoogle ScholarDigital LibraryDigital Library
  38. Leslie G. Valiant. 1979. The complexity of enumeration and reliability problems. SIAM J. Comput. 8, 3 (1979), 410--421.Google ScholarGoogle ScholarDigital LibraryDigital Library
  39. 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 ScholarGoogle Scholar
  40. 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 ScholarGoogle Scholar
  41. 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 ScholarGoogle Scholar
  42. Kai Zhu and Lei Ying. 2014. A robust information source estimator with sparse observations. Computational Social Networks 1, 1 (2014), 1--21.Google ScholarGoogle ScholarCross RefCross Ref

Index Terms

  1. Misinformation in Online Social Networks: Detect Them All with a Limited Budget

          Recommendations

          Comments

          Login options

          Check if you have access through your login credentials or your institution to get full access on this article.

          Sign in

          Full Access

          • Published in

            cover image ACM Transactions on Information Systems
            ACM Transactions on Information Systems  Volume 34, Issue 3
            Special Issue on Trust and Veracity of Information in Social Media
            May 2016
            110 pages
            ISSN:1046-8188
            EISSN:1558-2868
            DOI:10.1145/2915200
            Issue’s Table of Contents

            Copyright © 2016 ACM

            Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

            Publisher

            Association for Computing Machinery

            New York, NY, United States

            Publication History

            • Published: 11 April 2016
            • Accepted: 1 January 2016
            • Revised: 1 December 2015
            • Received: 1 April 2015
            Published in tois Volume 34, Issue 3

            Permissions

            Request permissions about this article.

            Request Permissions

            Check for updates

            Qualifiers

            • research-article
            • Research
            • Refereed

          PDF Format

          View or Download as a PDF file.

          PDF

          eReader

          View online with eReader.

          eReader