research-article

Public Access

Rumor Blocking through Online Link Deletion on Social Networks

Authors:

Yongcai WangAuthors Info & Claims

ACM Transactions on Knowledge Discovery from Data (TKDD), Volume 13, Issue 2

Article No.: 16, Pages 1 - 26

https://doi.org/10.1145/3301302

Published: 13 March 2019 Publication History

All formats PDF

Abstract

In recent years, social networks have become important platforms for people to disseminate information. However, we need to take effective measures such as blocking a set of links to control the negative rumors spreading over the network. In this article, we propose a Rumor Spread Minimization (RSM) problem, i.e., we remove an edge set from network such that the rumor spread is minimized. We first prove the objective function of RSM problem is not submodular. Then, we propose both submodular lower-bound and upper-bound of the objective function. Next, we develop a heuristic algorithm to approximate the objective function. Furthermore, we reformulate our objective function as the DS function (the Difference of Submodular functions). Finally, we conduct experiments on real-world datasets to evaluate our proposed method. The experiment results show that the upper and lower bounds are very close, which indicates the good quality of them. And, the proposed method outperforms the comparison methods.

References

[1]

Béla Bollobás. 1984. Graph Theory and Combinatorics: Proceedings of the Cambridge Combinatorial Conference in Honour of Paul Erdös,{Trinity College, Cambridge, 21--25 March 1983}. Academic Press.

[2]

Ceren Budak, Divyakant Agrawal, and Amr El Abbadi. 2011. Limiting the spread of misinformation in social networks. In Proceedings of the 20th International Conference on World Wide Web. ACM, 665--674.

Digital Library

[3]

Shai Carmi, Shlomo Havlin, Scott Kirkpatrick, Yuval Shavitt, and Eran Shir. 2007. A model of internet topology using k-shell decomposition. Proceedings of the National Academy of Sciences of the USA 104, 27 (2007), 11150--11154.

[4]

Wei Chen, Chi Wang, and Yajun Wang. 2010. Scalable influence maximization for prevalent viral marketing in large-scale social networks. In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 1029--1038.

Digital Library

[5]

Wei Chen, Yajun Wang, and Siyu Yang. 2009. Efficient influence maximization in social networks. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 199--208.

Digital Library

[6]

Cesar Henrique Comin and Luciano da Fontoura Costa. 2011. Identifying the starting point of a spreading process in complex networks. Physical Review E 84, 5 (2011), 056105.

[7]

Benjamin Doerr, Mahmoud Fouz, and Tobias Friedrich. 2012. Why rumors spread so quickly in social networks. Communications of the ACM 55, 6 (2012), 70--75.

Digital Library

[8]

Pedro Domingos and Matt Richardson. 2001. Mining the network value of customers. In Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 57--66.

Digital 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 33rd International Conference on Distributed Computing Systems (ICDCS’03). IEEE, 540--549.

Digital Library

[10]

Rishabh Iyer and Jeff Bilmes. 2012. Algorithms for approximate minimization of the difference between submodular functions, with applications. In Twenty-Eighth Conference on Uncertainty in Artificial Intelligence.

Digital Library

[11]

Rishabh Iyer, Stefanie Jegelka, and Jeff Bilmes. 2013. Fast semidifferential-based submodular function optimization. In Proceedings of the International Conference on Machine Learning. 855--863.

Digital Library

[12]

David Kempe, Jon Kleinberg, and Éva Tardos. 2003. Maximizing the spread of influence through a social network. In Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 137--146.

Digital Library

[13]

Elias Boutros Khalil, Bistra Dilkina, and Le Song. 2014. Scalable diffusion-aware optimization of network topology. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 1226--1235.

Digital Library

[14]

Masahiro Kimura, Kazumi Saito, and Hiroshi Motoda. 2008. Minimizing the spread of contamination by blocking links in a network. In Proceedings of the 23nd AAAI Conference of Artificial Intelligence. AAAI, 1175--1180.

Digital Library

[15]

Maksim Kitsak, Lazaros K. Gallos, Shlomo Havlin, Fredrik Liljeros, Lev Muchnik, H. Eugene Stanley, and Hernán A. Makse. 2010. Identification of influential spreaders in complex networks. Nature Physics 6, 11 (2010), 888.

[16]

Wei Lu, Wei Chen, and Laks V. S. Lakshmanan. 2015. From competition to complementarity: Comparative influence diffusion and maximization. Proceedings of the VLDB Endowment 9, 2 (2015), 60--71.

Digital Library

[17]

Mukund Narasimhan and Jeff A. Bilmes. 2012. A submodular-supermodular procedure with applications to discriminative structure learning. arXiv:1207.1404 (2012).

[18]

M. E. J. Newman, Stephanie Forrest, and Justin Balthrop. 2002. Email networks and the spread of computer viruses. Physical Review E 66 (2002), 035101, 1--4.

[19]

Nam P. Nguyen, Guanhua Yan, My T. Thai, and Stephan Eidenbenz. 2012. Containment of misinformation spread in online social networks. In Proceedings of the 4th Annual ACM Web Science Conference. ACM, 213--222.

Digital Library

[20]

Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. 1998. The Pagerank Citation Ranking: Bringing Order to the Web. Technical Report. Stanford InfoLab.

[21]

Guangmo Tong, Weili Wu, Ling Guo, Deying Li, Cong Liu, Bin Liu, and Ding-Zhu Du. 2017. An efficient randomized algorithm for rumor blocking in online social networks. IEEE Transactions on Network Science and Engineering.

[22]

Guangmo Amo Tong, Weili Wu, and Ding-Zhu Du. 2017. Distributed rumor blocking with multiple positive cascades. In IEEE Transactions on Computational Social Systems PP 99 (2017), 1--13.

[23]

Hanghang Tong, B. Aditya Prakash, Tina Eliassi-Rad, Michalis Faloutsos, and Christos Faloutsos. 2012. Gelling, and melting, large graphs by edge manipulation. In Proceedings of the 21st ACM International Conference on Information and Knowledge Management. ACM, 245--254.

Digital Library

[24]

Senzhang Wang, Xiaojian Zhao, Yan Chen, Zhoujun Li, Kai Zhang, and Jiali Xia. 2013. Negative influence minimizing by blocking nodes in social networks. In Proceedings of the 27th AAAI Conference on Artificial Intelligence (Late-Breaking Developments) (AAAI’13). 134--136.

Digital Library

[25]

Ruidong Yan, Yuqing Zhu, Deying Li, and Zilong Ye. 2018. Minimum cost seed set for threshold influence problem under competitive models. World Wide Web (2018), 1--20.

[26]

Qipeng Yao, Chuan Zhou, Linbo Xiang, Yanan Cao, and Li Guo. 2014. Minimizing the negative influence by blocking links in social networks. In Proceedings of the International Conference on Trustworthy Computing and Services (ISCTCS’14). CCIS, vol. 520, 65--73.

[27]

Arkaitz Zubiaga, Maria Liakata, Rob Procter, Geraldine Wong Sak Hoi, and Peter Tolmie. 2016. Analysing how people orient to and spread rumours in social media by looking at conversational threads. PLoS One 11, 3 (2016) e0150989, 1--29.

Cited By

He QZhang ZBi TFang HYi XYu K(2025)Adaptive Rumor Suppression on Social Networks: A Multi-Round Hybrid ApproachACM Transactions on Knowledge Discovery from Data10.1145/370173819:2(1-24)Online publication date: 11-Jan-2025
https://dl.acm.org/doi/10.1145/3701738
Huang YGao MShu KLin CWang JZhou W(2024)EML: Emotion-Aware Meta Learning for Cross-Event False Information DetectionACM Transactions on Knowledge Discovery from Data10.1145/366148518:8(1-25)Online publication date: 2-May-2024
https://dl.acm.org/doi/10.1145/3661485
Gao FWang XHe Q(2024)Multi-Feature Rumor Suppression Mechanism Based on Community Division in Social NetworksIEEE Transactions on Network Science and Engineering10.1109/TNSE.2023.333664911:2(2047-2061)Online publication date: Mar-2024
https://doi.org/10.1109/TNSE.2023.3336649
Show More Cited By

Index Terms

Rumor Blocking through Online Link Deletion on Social Networks
1. Networks
  1. Network algorithms
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Rumor blocking with pertinence set in large graphs
Abstract
Online social networks facilitate the spread of information, while rumors can also propagate widely and fast, which may mislead some users. Therefore, suppressing the spread of rumors has become a daunting task. One of the widely used approaches ...
Stochastic Model for Rumor Blocking Problem in Social Networks Under Rumor Source Uncertainty
Computing and Combinatorics
Abstract
Either in real world social society or online social networks, rumor blocking is an important issue. Rumor sources spread negative information throughout the network, which may cause unbelievable results in real society, such as panic, unrest. ... $_{}$ $_{}$
Rumor Remove Order Strategy on Social Networks
ICISDM '21: Proceedings of the 2021 5th International Conference on Information System and Data Mining

Rumors are defined as widely spread talk with no reliable source to back it up. In modern society, the rumors are widely spreading on the social network. The spread of rumors poses great challenges for the society. A ”fake news” story can rile up your ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Knowledge Discovery from Data

ACM Transactions on Knowledge Discovery from Data Volume 13, Issue 2

April 2019

342 pages

ISSN:1556-4681

EISSN:1556-472X

DOI:10.1145/3319626

Editors:
Charu Aggarwal
IBM T. J. Watson Research, USA
,
Xindong Wu
University of Louisiana at Lafayette, USA

Issue’s Table of Contents

Copyright © 2019 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: 13 March 2019

Accepted: 01 December 2018

Revised: 01 November 2018

Received: 01 August 2018

Published in TKDD Volume 13, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Fundamental Research Funds for the Central University, and the Research Funds of Renmin University of China
National Natural Science Foundation of China
National Science Foundation

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

53
Total Citations
View Citations
1,521
Total Downloads

Downloads (Last 12 months)219
Downloads (Last 6 weeks)25

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

He QZhang ZBi TFang HYi XYu K(2025)Adaptive Rumor Suppression on Social Networks: A Multi-Round Hybrid ApproachACM Transactions on Knowledge Discovery from Data10.1145/370173819:2(1-24)Online publication date: 11-Jan-2025
https://dl.acm.org/doi/10.1145/3701738
Huang YGao MShu KLin CWang JZhou W(2024)EML: Emotion-Aware Meta Learning for Cross-Event False Information DetectionACM Transactions on Knowledge Discovery from Data10.1145/366148518:8(1-25)Online publication date: 2-May-2024
https://dl.acm.org/doi/10.1145/3661485
Gao FWang XHe Q(2024)Multi-Feature Rumor Suppression Mechanism Based on Community Division in Social NetworksIEEE Transactions on Network Science and Engineering10.1109/TNSE.2023.333664911:2(2047-2061)Online publication date: Mar-2024
https://doi.org/10.1109/TNSE.2023.3336649
Liu CZhou XZehmakan AZhang Z(2024)A Fast Algorithm for Moderating Critical Nodes via Edge RemovalIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.330998736:4(1385-1398)Online publication date: Apr-2024
https://doi.org/10.1109/TKDE.2023.3309987
Gao FHe QWang XQiu LHuang M(2024)An Efficient Rumor Suppression Approach With Knowledge Graph Convolutional Network in Social NetworkIEEE Transactions on Computational Social Systems10.1109/TCSS.2024.338349311:5(6254-6267)Online publication date: Oct-2024
https://doi.org/10.1109/TCSS.2024.3383493
Bouyer ABeni HOskouei ARouhi AArasteh BLiu X(2024)Maximizing Influence in Social Networks Using Combined Local Features and Deep Learning-Based Node EmbeddingBig Data10.1089/big.2023.0117Online publication date: 22-Oct-2024
https://doi.org/10.1089/big.2023.0117
Dong 董 CXu 徐 GMeng 孟 L(2024)CRB: A new rumor blocking algorithm in online social networks based on competitive spreading model and influence maximizationChinese Physics B10.1088/1674-1056/ad531f33:8(088901)Online publication date: 1-Aug-2024
https://doi.org/10.1088/1674-1056/ad531f
López SMolina ESaboyá MTejada J(2024)Node centrality based on its edges importance: The Position centralityMathematical Social Sciences10.1016/j.mathsocsci.2024.10.001132(90-104)Online publication date: Dec-2024
https://doi.org/10.1016/j.mathsocsci.2024.10.001
Ni PZhu JGao YWang G(2024)Minimizing the misinformation concern over social networksInformation Processing & Management10.1016/j.ipm.2023.10356261:1(103562)Online publication date: Jan-2024
https://doi.org/10.1016/j.ipm.2023.103562
Yu LWang XYu H(2024)Misinformation blocking maximization in online social networksMultimedia Tools and Applications10.1007/s11042-023-17979-y83:23(62853-62874)Online publication date: 9-Jan-2024
https://doi.org/10.1007/s11042-023-17979-y
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Login options

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

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents