{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,4,14]],"date-time":"2024-04-14T12:28:19Z","timestamp":1713097699221},"reference-count":70,"publisher":"Oxford University Press (OUP)","issue":"9","license":[{"start":{"date-parts":[[2022,7,5]],"date-time":"2022-07-05T00:00:00Z","timestamp":1656979200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,9,18]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>We consider misinformation propagating through a social network and study the problem of its prevention. The goal is to identify a set of $k$ users that need to be convinced to adopt a limiting campaign so as to minimize the number of people that end up adopting the misinformation. This work presents Reverse Prevention Sampling (RPS), an algorithm that provides a scalable solution to the misinformation mitigation problem. Our theoretical analysis shows that RPS runs in $O((k + l)(n + m)(\\frac{1}{1 - \\gamma }) \\log n \/ \\epsilon ^2 )$ expected time and returns a $(1 - 1\/e - \\epsilon )$-approximate solution with at least $1 - n^{-l}$ probability (where $\\gamma $ is a typically small network parameter and $l$ is a confidence parameter). The time complexity of RPS substantially improves upon the previously best-known algorithms that run in time $\\Omega (m n k \\cdot POLY(\\epsilon ^{-1}))$. We experimentally evaluate RPS on large datasets and show that it outperforms the state-of-the-art solution by several orders of magnitude in terms of running time. This demonstrates that misinformation mitigation can be made practical while still offering strong theoretical guarantees.<\/jats:p>","DOI":"10.1093\/comjnl\/bxac073","type":"journal-article","created":{"date-parts":[[2022,7,6]],"date-time":"2022-07-06T14:07:02Z","timestamp":1657116422000},"page":"2230-2253","source":"Crossref","is-referenced-by-count":1,"title":["Scalable Misinformation Mitigation in Social Networks Using Reverse Sampling"],"prefix":"10.1093","volume":"66","author":[{"given":"Michael","family":"Simpson","sequence":"first","affiliation":[{"name":"University of British Columbia , Vancouver, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Venkatesh","family":"Srinivasan","sequence":"additional","affiliation":[{"name":"University of Victoria , Victoria, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alex","family":"Thomo","sequence":"additional","affiliation":[{"name":"University of Victoria , Victoria, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2022,7,5]]},"reference":[{"key":"2023091720461198400_ref1","article-title":"\u2018bogus\u2019 ap tweet about explosion at the white house wipes billions off us markets","author":"Foster","year":"2018"},{"key":"2023091720461198400_ref2","volume-title":"Youtube shooting: Twitter and facebook explodes with misinformation and hoaxes","author":"Oppenheim","year":"2018"},{"key":"2023091720461198400_ref3","volume-title":"Youtube employee\u2019s twitter account hacked to spread fake news during attack","author":"Graham","year":"2018"},{"key":"2023091720461198400_ref4","volume-title":"Reddit was a misinformation hotspot in 2016 election, study says","author":"Hautala","year":"2018"},{"key":"2023091720461198400_ref5","volume-title":"Facebook\u2019s failure: did fake news and polarized politics get trump elected?","author":"Solon","year":"2018"},{"key":"2023091720461198400_ref6","volume-title":"Troll factories, bots and fake news: Inside the wild west of social media","author":"Abeshouse","year":"2018"},{"key":"2023091720461198400_ref7","doi-asserted-by":"crossref","first-page":"665","DOI":"10.1145\/1963405.1963499","article-title":"Limiting the spread of misinformation in social networks","volume-title":"Proceedings of the 20th International Conference on World Wide Web","author":"Budak","year":"2011"},{"key":"2023091720461198400_ref8","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1145\/956750.956769","article-title":"Maximizing the spread of influence through a social network","volume-title":"Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining","author":"Kempe","year":"2003"},{"key":"2023091720461198400_ref9","first-page":"946","article-title":"Maximizing social influence in nearly optimal time","volume-title":"Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms","author":"Borgs","year":"2014"},{"key":"2023091720461198400_ref10","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1145\/2588555.2593670","article-title":"Influence maximization: Near-optimal time complexity meets practical efficiency","volume-title":"Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data","author":"Tang","year":"2014"},{"key":"2023091720461198400_ref11","doi-asserted-by":"crossref","first-page":"1539","DOI":"10.1145\/2723372.2723734","article-title":"Influence maximization in near-linear time: A martingale approach","volume-title":"Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data","author":"Tang","year":"2015"},{"key":"2023091720461198400_ref12","first-page":"918","article-title":"Irie: Scalable and robust influence maximization in social networks","volume-title":"ICDM \u201812","author":"Jung","year":"2012"},{"key":"2023091720461198400_ref13","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1007\/s10618-012-0262-1","article-title":"Scalable influence maximization for independent cascade model in large-scale social networks","volume":"25","author":"Wang","year":"2012","journal-title":"Data Mining and Knowledge Discovery"},{"key":"2023091720461198400_ref14","doi-asserted-by":"crossref","first-page":"641","DOI":"10.1145\/1772690.1772756","article-title":"Predicting positive and negative links in online social networks","volume-title":"Proceedings of the 19th International Conference on World Wide Web","author":"Leskovec","year":"2010"},{"key":"2023091720461198400_ref15","doi-asserted-by":"crossref","DOI":"10.1109\/ICDM.2010.118","article-title":"Scalable influence maximization in social networks under the linear threshold model","volume-title":"ICDM \u201810","author":"Chen","year":"2010"},{"key":"2023091720461198400_ref16","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1007\/s13278-012-0062-z","article-title":"On minimizing budget and time in influence propagation over social networks","volume":"3","author":"Goyal","year":"2013","journal-title":"Social Netw. Analys. Mining"},{"key":"2023091720461198400_ref17","doi-asserted-by":"crossref","first-page":"695","DOI":"10.1145\/2882903.2915207","article-title":"Stop-and-stare: Optimal sampling algorithms for viral marketing in billion-scale networks","volume-title":"Proceedings of the 2016 International Conference on Management of Data","author":"Nguyen","year":"2016"},{"key":"2023091720461198400_ref18","doi-asserted-by":"crossref","first-page":"913","DOI":"10.14778\/3099622.3099623","article-title":"Revisiting the stop-and-stare algorithms for influence maximization","volume":"10","author":"Huang","year":"2017","journal-title":"Proceedings of the VLDB Endowment"},{"key":"2023091720461198400_ref19","doi-asserted-by":"crossref","first-page":"991","DOI":"10.1145\/3183713.3183749","article-title":"Online processing algorithms for influence maximization","volume-title":"Proceedings of the 2018 International Conference on Management of Data","author":"Tang","year":"2018"},{"key":"2023091720461198400_ref20","first-page":"306","article-title":"Competitive influence maximization in social networks","volume-title":"International workshop on web and internet economics","author":"Bharathi","year":"2007"},{"key":"2023091720461198400_ref21","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/j.peva.2015.06.012","article-title":"Analyzing competitive influence maximization problems with partial information: An approximation algorithmic framework","volume":"91","author":"Lin","year":"2015","journal-title":"Performance Evaluation"},{"key":"2023091720461198400_ref22","first-page":"965","article-title":"A generalized linear threshold model for multiple cascades","volume-title":"ICDM \u201810","author":"Pathak","year":"2010"},{"key":"2023091720461198400_ref23","first-page":"657","article-title":"Influence diffusion dynamics and influence maximization in social networks with friend and foe relationships","volume-title":"WSDM \u201813","author":"Li","year":"2013"},{"key":"2023091720461198400_ref24","first-page":"463","article-title":"Influence blocking maximization in social networks under the competitive linear threshold model","volume-title":"SDM \u201812","author":"He","year":"2012"},{"key":"2023091720461198400_ref25","first-page":"540","article-title":"Least cost rumor blocking in social networks","volume-title":"ICDCS \u201813","author":"Fan","year":"2013"},{"key":"2023091720461198400_ref26","doi-asserted-by":"crossref","first-page":"847","DOI":"10.1109\/ICDE.2017.134","article-title":"Temporal influence blocking: Minimizing the effect of misinformation in social networks","volume-title":"2017 IEEE 33rd International Conference on Data Engineering (ICDE)","author":"Song","year":"2017"},{"key":"2023091720461198400_ref27","first-page":"341","article-title":"On misinformation containment in online social networks","author":"Tong","year":"2018","journal-title":"Advances in neural information processing systems"},{"key":"2023091720461198400_ref28","doi-asserted-by":"crossref","first-page":"1711","DOI":"10.1109\/INFOCOM.2019.8737485","article-title":"Beyond uniform reverse sampling: A hybrid sampling technique for misinformation prevention","volume-title":"IEEE INFOCOM 2019-IEEE conference on computer communications","author":"Tong","year":"2019"},{"key":"2023091720461198400_ref29","doi-asserted-by":"crossref","first-page":"845","DOI":"10.1109\/TNSE.2017.2783190","article-title":"An efficient randomized algorithm for rumor blocking in online social networks","volume":"7","author":"Tong","year":"2017","journal-title":"IEEE Transactions on Network Science and Engineering"},{"key":"2023091720461198400_ref30","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1145\/3366424.3383297","article-title":"Mitigating misinformation in online social network with top-k debunkers and evolving user opinions","volume-title":"Companion Proceedings of the Web Conference 2020","author":"Saxena","year":"2020"},{"key":"2023091720461198400_ref31","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1007\/978-3-319-75417-8_10","article-title":"Targeted misinformation blocking on online social networks","volume-title":"Asian Conference on Intelligent Information and Database Systems","author":"Pham","year":"2018"},{"key":"2023091720461198400_ref32","doi-asserted-by":"crossref","first-page":"1101","DOI":"10.1007\/s10878-019-00439-5","article-title":"Minimum budget for misinformation blocking in online social networks","volume":"38","author":"Pham","year":"2019","journal-title":"Journal of Combinatorial Optimization"},{"key":"2023091720461198400_ref33","first-page":"161","article-title":"General rumor blocking: An efficient random algorithm with martingale approach","volume-title":"International Conference on Algorithmic Applications in Management","author":"Fang","year":"2018"},{"key":"2023091720461198400_ref34","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1007\/s10115-012-0520-y","article-title":"Threshold conditions for arbitrary cascade models on arbitrary networks","volume":"33","author":"Prakash","year":"2012","journal-title":"Knowledge and information systems"},{"key":"2023091720461198400_ref35","first-page":"659","article-title":"Fractional immunization in networks","volume-title":"Proceedings of the 2013 SIAM International Conference on Data Mining","author":"Prakash","year":"2013"},{"key":"2023091720461198400_ref36","first-page":"46","article-title":"Dava: Distributing vaccines over networks under prior information","volume-title":"Proceedings of the 2014 SIAM International Conference on Data Mining","author":"Zhang","year":"2014"},{"key":"2023091720461198400_ref37","doi-asserted-by":"crossref","first-page":"1435","DOI":"10.1109\/TKDE.2016.2525993","article-title":"Clearing contamination in large networks","volume":"28","author":"Simpson","year":"2016","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"2023091720461198400_ref38","first-page":"245","article-title":"Gelling, and melting, large graphs by edge manipulation","author":"Tong","year":"2012","journal-title":"CIKM"},{"key":"2023091720461198400_ref39","article-title":"Influence minimization under budget and matroid constraints: Extended version","author":"Medya","year":"2019"},{"key":"2023091720461198400_ref40","doi-asserted-by":"crossref","first-page":"1226","DOI":"10.1145\/2623330.2623704","article-title":"Scalable diffusion-aware optimization of network topology","volume-title":"Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining","author":"Khalil","year":"2014"},{"key":"2023091720461198400_ref41","first-page":"113","article-title":"Node immunization on large graphs: Theory and algorithms","volume":"28","author":"Chen","year":"2015","journal-title":"TKDE"},{"key":"2023091720461198400_ref42","doi-asserted-by":"crossref","first-page":"1667","DOI":"10.1007\/s10115-018-01326-x","article-title":"Data-driven efficient network and surveillance-based immunization","volume":"61","author":"Zhang","year":"2019","journal-title":"Knowledge and Information Systems"},{"key":"2023091720461198400_ref43","volume-title":"How is facebook addressing false news?","author":"Facebook","year":"2019"},{"key":"2023091720461198400_ref44","volume-title":"Helping to protect the 2020 us elections","author":"Facebook","year":"2019"},{"key":"2023091720461198400_ref45","volume-title":"Notices on twitter and what they mean","author":"Twitter","year":"2020"},{"key":"2023091720461198400_ref46","volume-title":"Our range of enforcement options","author":"Twitter","year":"2020"},{"key":"2023091720461198400_ref47","volume-title":"Instagram adds \u2018false information\u2019 labels to prevent fake news from going viral","author":"Instagram","year":"2019"},{"key":"2023091720461198400_ref48","volume-title":"Health misinformation","author":"Pinterest","year":"2019"},{"key":"2023091720461198400_ref49","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1145\/3137597.3137600","article-title":"Fake news detection on social media: A data mining perspective","volume":"19","author":"Shu","year":"2017","journal-title":"ACM SIGKDD Explorations Newsletter"},{"key":"2023091720461198400_ref50","doi-asserted-by":"crossref","first-page":"2807","DOI":"10.1145\/3219819.3219968","article-title":"Sparc: Self-paced network representation for few-shot rare category characterization","volume-title":"Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining","author":"Zhou","year":"2018"},{"key":"2023091720461198400_ref51","doi-asserted-by":"crossref","first-page":"655","DOI":"10.1145\/3097983.3098015","article-title":"A local algorithm for structure-preserving graph cut","volume-title":"Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining","author":"Zhou","year":"2017"},{"key":"2023091720461198400_ref52","first-page":"1945","article-title":"Claimbuster: The first-ever end-to-end fact-checking system","volume":"10","author":"Hassan","year":"2017","journal-title":"PVLDB"},{"key":"2023091720461198400_ref53","first-page":"517","article-title":"Fake news detection in social networks via crowd signals","volume-title":"WWW \u201818","author":"Tschiatschek","year":"2018"},{"key":"2023091720461198400_ref54","doi-asserted-by":"crossref","DOI":"10.2139\/ssrn.3118471","article-title":"Crowdsourcing judgments of news source quality","author":"Pennycook","year":"2018","journal-title":"SSRN."},{"key":"2023091720461198400_ref55","first-page":"324","article-title":"Leveraging the crowd to detect and reduce the spread of fake news and misinformation","volume-title":"WSDM \u201818","author":"Kim","year":"2018"},{"key":"2023091720461198400_ref56","doi-asserted-by":"crossref","first-page":"881","DOI":"10.14778\/2732951.2732962","article-title":"From data fusion to knowledge fusion","volume":"7","author":"Dong","year":"2014","journal-title":"Proceedings of the VLDB Endowment"},{"key":"2023091720461198400_ref57","doi-asserted-by":"crossref","first-page":"2048","DOI":"10.14778\/2824032.2824136","article-title":"Truth discovery and crowdsourcing aggregation: A unified perspective","volume":"8","author":"Gao","year":"2015","journal-title":"Proceedings of the VLDB Endowment"},{"key":"2023091720461198400_ref58","doi-asserted-by":"crossref","first-page":"1399","DOI":"10.1145\/3035918.3035951","article-title":"Slimfast: Guaranteed results for data fusion and source reliability","volume-title":"Proceedings of the 2017 ACM International Conference on Management of Data","author":"Rekatsinas","year":"2017"},{"key":"2023091720461198400_ref59","first-page":"859","article-title":"Finding streams in knowledge graphs to support fact checking","volume-title":"ICDM \u201817","author":"Shiralkar","year":"2017"},{"key":"2023091720461198400_ref60","doi-asserted-by":"crossref","first-page":"990","DOI":"10.1109\/ICDE.2016.7498307","article-title":"Fast top-k search in knowledge graphs","volume-title":"2016 IEEE 32nd international conference on data engineering (ICDE)","author":"Yang","year":"2016"},{"key":"2023091720461198400_ref61","first-page":"2026","article-title":"Embedding logical queries on knowledge graphs","author":"Hamilton","year":"2018","journal-title":"Advances in neural information processing systems"},{"key":"2023091720461198400_ref62","article-title":"Computational fact checking from knowledge networks","volume":"10","author":"Ciampaglia","year":"2015","journal-title":"PloS one"},{"key":"2023091720461198400_ref63","first-page":"1003","article-title":"Where the truth lies: Explaining the credibility of emerging claims on the web and social media","volume-title":"WWW \u201817","author":"Popat","year":"2017"},{"key":"2023091720461198400_ref64","first-page":"2972","article-title":"News verification by exploiting conflicting social viewpoints in microblogs","volume-title":"AAAI \u201816","author":"Jin","year":"2016"},{"key":"2023091720461198400_ref65","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1145\/2806416.2806537","article-title":"Leveraging joint interactions for credibility analysis in news communities","volume-title":"Proceedings of the 24th ACM International on Conference on Information and Knowledge Management","author":"Mukherjee","year":"2015"},{"key":"2023091720461198400_ref66","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1145\/2380718.2380746","article-title":"Containment of misinformation spread in online social networks","volume-title":"Proceedings of the 4th Annual ACM Web Science Conference","author":"Nguyen","year":"2012"},{"key":"2023091720461198400_ref67","volume-title":"Information and Influence Propagation in Social Networks Synthesis Lectures on Data Management","author":"Chen","year":"2013"},{"key":"2023091720461198400_ref68","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/BF01588971","article-title":"An analysis of approximations for maximizing submodular set functions\u2014i","volume":"14","author":"Nemhauser","year":"1978","journal-title":"Mathematical Programming"},{"key":"2023091720461198400_ref69","first-page":"222","article-title":"Probabilistic computations: Toward a unified measure of complexity","volume-title":"Proceedings of the 18th Annual Symposium on Foundations of Computer Science","author":"Yao","year":"1977"},{"key":"2023091720461198400_ref70","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1145\/1557019.1557047","article-title":"Efficient influence maximization in social networks","volume-title":"Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining","author":"Chen","year":"2009"}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/66\/9\/2230\/51643474\/bxac073.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/66\/9\/2230\/51643474\/bxac073.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,17]],"date-time":"2023-09-17T21:10:02Z","timestamp":1694985002000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/66\/9\/2230\/6631439"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,5]]},"references-count":70,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2022,7,5]]},"published-print":{"date-parts":[[2023,9,18]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxac073","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"value":"0010-4620","type":"print"},{"value":"1460-2067","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2023,9]]},"published":{"date-parts":[[2022,7,5]]}}}