The DOI matches its Crossref record; 37 of the 37 references it cites were found in a registry or an index.
Limiting the spread of misinformation in social networks
Abstract
In this work, we study the notion of competing campaigns in a social network and address the problem of influence limitation where a "bad" campaign starts propagating from a certain node in the network and use the notion of limiting campaigns to counteract the effect of misinformation. The problem can be summarized as identifying a subset of individuals that need to be convinced to adopt the competing (or "good") campaign so as to minimize the number of people that adopt the "bad" campaign at the end of both propagation processes. We show that this optimization problem is NP-hard and provide approximation guarantees for a greedy solution for various definitions of this problem by proving that they are submodular. We experimentally compare the performance of the greedy method to various heuristics. The experiments reveal that in most cases inexpensive heuristics such as degree centrality compare well with the greedy approach. We also study the influence limitation problem in the presence of missing data where the current states of nodes in the network are only known with a certain probability and show that prediction in this setting is a supermodular problem. We propose a prediction algorithm that is based on generating random spanning trees and evaluate the performance of this approach. The experiments reveal that using the prediction algorithm, we are able to tolerate about 90% missing data before the performance of the algorithm starts degrading and even with large amounts of missing data the performance degrades only to 75% of the performance that would be achieved with complete data.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Social Network Analysis: Methods and Applications
Wasserman, S. S., & Faust, K. (1994) · Cited by 17,993
Social Network Analysis: Methods and Applications
Wasserman, S., & Faust, K. (1994) · doi:10.1017/cbo9780511815478 · Cited by 17,557
Infectious Diseases of Humans: Dynamics and Control
(1992) · Annals of Internal Medicine · doi:10.7326/0003-4819-117-2-174_4 · Cited by 7,746
Maximizing the spread of influence through a social network
Kempe, D., Kleinberg, J., & Tardos, É. (2003) · Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/956750.956769 · Cited by 7,326
The Mathematics of Infectious Diseases
Hethcote, H. W. (2000) · SIAM Review · doi:10.1137/s0036144500371907 · Cited by 6,687
Threshold models of collective behavior
Granovetter, M. (1978) · American Journal of Sociology · doi:10.1086/226707 · Cited by 6,072
(2017) · The SAGE Encyclopedia of Communication Research Methods · doi:10.4135/9781483381411.n575 · Cited by 6,008
An analysis of approximations for maximizing submodular set functions—I
Nemhauser, G. L., Wolsey, L. A., & Fisher, M. L. (1978) · Mathematical Programming · doi:10.1007/bf01588971 · Cited by 4,412
(2016) · Foundations of Physically Based Modeling and Animation · doi:10.1201/9781315373140-16 · Cited by 3,267
Identification of influential spreaders in complex networks
Kitsak, M., Gallos, L. K., Havlin, S., Liljeros, F., Muchnik, L., Stanley, H. E., & Makse, H. A. (2010) · Nature Physics · doi:10.1038/nphys1746 · Cited by 3,212
Cited by
Inoculating the Public against Misinformation about Climate Change
van der Linden, S., Leiserowitz, A., Rosenthal, S., & Maibach, E. (2017) · Global Challenges · doi:10.1002/gch2.201600008 · Cited by 1,058
Countering Misinformation and Fake News Through Inoculation and Prebunking
Lewandowsky, S., & van der Linden, S. (2021) · European Review of Social Psychology · doi:10.1080/10463283.2021.1876983 · Cited by 773
A Stylometric Inquiry into Hyperpartisan and Fake News
Potthast, M., Kiesel, J., Reinartz, K., Bevendorff, J., & Stein, B. (2018) · Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) · doi:10.18653/v1/p18-1022 · Cited by 686
Influence Maximization on Social Graphs: A Survey
Li, Y., Fan, J., Wang, Y., & Tan, K.-L. (2018) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2018.2807843 · Cited by 659
Combating Fake News: A Survey on Identification and Mitigation Techniques
Sharma, K., Qian, F., Jiang, H., Ruchansky, N., Zhang, M., & Liu, Y. (2019) · ACM Transactions on Intelligent Systems and Technology · doi:10.1145/3305260 · Cited by 514
“[11] showed that a similar greedy algorithm as discussed in Section 6.”
MethodDynamics of information diffusion and its applications on complex networks
Zhang, Z.-K., Liu, C., Zhan, X.-X., Lu, X., Zhang, C.-X., & Zhang, Y.-C. (2016) · Physics Reports · doi:10.1016/j.physrep.2016.07.002 · Cited by 484
The fake news game: actively inoculating against the risk of misinformation
Roozenbeek, J., & van der Linden, S. (2019) · Journal of Risk Research · doi:10.1080/13669877.2018.1443491 · Cited by 479
Online misinformation about climate change
Treen, K. M. D., Williams, H. T. P., & O'Neill, S. J. (2020) · WIREs Climate Change · doi:10.1002/wcc.665 · Cited by 441
Influence Blocking Maximization in Social Networks under the Competitive Linear Threshold Model
He, X., Song, G., Chen, W., & Jiang, Q. (2012) · Proceedings of the 2012 SIAM International Conference on Data Mining · doi:10.1137/1.9781611972825.40 · Cited by 403
Epidemiological modeling of news and rumors on Twitter
Jin, F., Dougherty, E., Saraf, P., Cao, Y., & Ramakrishnan, N. (2013) · Proceedings of the 7th Workshop on Social Network Mining and Analysis · doi:10.1145/2501025.2501027 · Cited by 342
Disinformation on the Web: Impact, Characteristics, and Detection of Wikipedia Hoaxes
Kumar, S., West, R., & Leskovec, J. (2016) · Proceedings of the 25th International Conference on World Wide Web · doi:10.1145/2872427.2883085 · Cited by 310
Fighting an Infodemic: COVID-19 Fake News Dataset
Patwa, P., Sharma, S., Pykl, S., Guptha, V., Kumari, G., Akhtar, M. S., Ekbal, A., Das, A., & Chakraborty, T. (2021) · Communications in Computer and Information Science · doi:10.1007/978-3-030-73696-5_3 · Cited by 271
Socially Responsible AI Algorithms: Issues, Purposes, and Challenges
Cheng, L., Varshney, K. R., & Liu, H. (2021) · Journal of Artificial Intelligence Research · doi:10.1613/jair.1.12814 · Cited by 261
Why Students Share Misinformation on Social Media: Motivation, Gender, and Study-level Differences
Chen, X., Sin, S.-C. J., Theng, Y.-L., & Lee, C. S. (2015) · The Journal of Academic Librarianship · doi:10.1016/j.acalib.2015.07.003 · Cited by 260
Spreading Processes in Multilayer Networks
Salehi, M., Sharma, R., Marzolla, M., Magnani, M., Siyari, P., & Montesi, D. (2015) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2015.2425961 · Cited by 255
Information and Influence Propagation in Social Networks
Chen, W., Lakshmanan, L. V. S., & Castillo, C. (2013) · Synthesis lectures on data management · doi:10.2200/s00527ed1v01y201308dtm037 · Cited by 254
Combating disinformation in a social media age
Shu, K., Bhattacharjee, A., Alatawi, F., Nazer, T. H., Ding, K., Karami, M., & Liu, H. (2020) · WIREs Data Mining and Knowledge Discovery · doi:10.1002/widm.1385 · Cited by 198
Characterizing Online Rumoring Behavior Using Multi-Dimensional Signatures
Maddock, J., Starbird, K., Al-Hassani, H. J., Sandoval, D. E., Orand, M., & Mason, R. M. (2015) · Proceedings of the 18th ACM Conference on Computer Supported Cooperative Work & Social Computing · doi:10.1145/2675133.2675280 · Cited by 129
“Existing research on the spread of rumors online is primarily quantitative, including descriptive studies of trace data [9,15,26], theoretical research on network factors [4,7], and prescriptive studies that experiment with machine learning methods to classify rumors as true or false [5,15,24].”
BackgroundThe Future of False Information Detection on Social Media: New Perspectives and Trends
Guo, B., Ding, Y., Yao, L., Liang, Y., & Yu, Z. (2021) · ACM Computing Surveys · doi:10.1145/3393880 · Cited by 122
The Web of False Information: Rumors, Fake News, Hoaxes, Clickbait, and Various Other Shenanigans
Zannettou, S., Sirivianos, M., Blackburn, J., & Kourtellis, N. (2019) · Journal of Data and Information Quality · doi:10.1145/3309699 · Cited by 86
Why Do Social Media Users Share Misinformation?
Chen, X., Sin, S.-C. J., Theng, Y.-L., & Lee, C. S. (2015) · Proceedings of the 15th ACM/IEEE-CS Joint Conference on Digital Libraries · doi:10.1145/2756406.2756941 · Cited by 70
Simulating Opinion Dynamics with Networks of LLM-based Agents
Chuang, Y.-S., Goyal, A., Harlalka, N., Suresh, S., Hawkins, R., Yang, S., Shah, D., Hu, J., & Rogers, T. (2024) · Findings of the Association for Computational Linguistics: NAACL 2024 · doi:10.18653/v1/2024.findings-naacl.211 · Cited by 85
Metadata
- Authors
- Budak, C., Agrawal, D., & El Abbadi, A.
- Venue
- Proceedings of the 20th international conference on World wide web
- Publisher
- ACM
- Published
- 2011-03-28
- Pages
- 665-674
- OpenAlex
- W2139297408
- Cited by
- 807
- References
- 37
- FWCI
- 36.43
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.