{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,7]],"date-time":"2026-08-07T07:59:27Z","timestamp":1786089567670,"version":"3.56.0"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"10","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,6]]},"abstract":"<jats:p>\n            Given a graph\n            <jats:italic>G<\/jats:italic>\n            , a budget\n            <jats:italic>k<\/jats:italic>\n            and a misinformation seed set\n            <jats:italic>S, Influence Minimization<\/jats:italic>\n            (IMIN) via node blocking aims to find a set of\n            <jats:italic>k<\/jats:italic>\n            nodes to be blocked such that the expected spread of\n            <jats:italic>S<\/jats:italic>\n            is minimized. This problem finds important applications in suppressing the spread of misinformation and has been extensively studied in the literature. However, existing solutions for IMIN still incur significant computation overhead, especially when\n            <jats:italic>k<\/jats:italic>\n            becomes large. In addition, there is still no approximation solution with non-trivial theoretical guarantee for IMIN via node blocking prior to our work. In this paper, we conduct the first attempt to propose algorithms that yield data-dependent approximation guarantees. Based on the Sandwich framework, we first develop submodular and monotonic lower and upper bounds for our non-submodular objective function and prove the computation of proposed bounds is #P-hard. In addition, two advanced sampling methods are proposed to estimate the value of bounding functions. Moreover, we develop two novel martingale-based concentration bounds to reduce the sample complexity and design two non-trivial algorithms that provide (1 - 1\/\n            <jats:italic>e - \u03f5<\/jats:italic>\n            )-approximate solutions to our bounding functions. Comprehensive experiments on 9 real-world datasets are conducted to validate the efficiency and effectiveness of the proposed techniques. Compared with the state-of-the-art methods, our solutions can achieve up to two orders of magnitude speedup and provide theoretical guarantees for the quality of returned results.\n          <\/jats:p>","DOI":"10.14778\/3675034.3675042","type":"journal-article","created":{"date-parts":[[2024,8,6]],"date-time":"2024-08-06T22:19:11Z","timestamp":1722982751000},"page":"2501-2513","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":20,"title":["Efficient Influence Minimization via Node Blocking"],"prefix":"10.14778","volume":"17","author":[{"given":"Jinghao","family":"Wang","sequence":"first","affiliation":[{"name":"Zhejiang Gongshang University, University of Technology Sydney"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yanping","family":"Wu","sequence":"additional","affiliation":[{"name":"University of Technology Sydney"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiaoyang","family":"Wang","sequence":"additional","affiliation":[{"name":"The University of New South Wales"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ying","family":"Zhang","sequence":"additional","affiliation":[{"name":"Zhejiang Gongshang University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lu","family":"Qin","sequence":"additional","affiliation":[{"name":"University of Technology Sydney"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wenjie","family":"Zhang","sequence":"additional","affiliation":[{"name":"The University of New South Wales"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[{"name":"Shanghai Jiaotong University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,8,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01459088"},{"key":"e_1_2_1_2_1","volume-title":"Ullman","author":"Aho Alfred V.","year":"1972","unstructured":"Alfred V. Aho and Jeffrey D. Ullman. 1972. The theory of parsing, translation, and compiling. 1: Parsing. Prentice-Hall."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.3386\/w23089"},{"key":"e_1_2_1_4_1","volume-title":"ICML (Proceedings of Machine Learning Research)","volume":"70","author":"Bian Andrew An","year":"2017","unstructured":"Andrew An Bian, Joachim M. Buhmann, Andreas Krause, and Sebastian Tschiatschek. 2017. Guarantees for Greedy Maximization of Non-submodular Functions with Applications. In ICML (Proceedings of Machine Learning Research), Vol. 70. PMLR, 498--507."},{"key":"e_1_2_1_5_1","volume-title":"Maximizing Social Influence in Nearly Optimal Time","author":"Borgs Christian","unstructured":"Christian Borgs, Michael Brautbar, Jennifer T. Chayes, and Brendan Lucier. 2014. Maximizing Social Influence in Nearly Optimal Time. In SODA. SIAM, 946--957."},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Ceren Budak Divyakant Agrawal and Amr El Abbadi. 2011. Limiting the spread of misinformation in social networks. In WWW. ACM 665--674.","DOI":"10.1145\/1963405.1963499"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Vineet Chaoji Sayan Ranu Rajeev Rastogi and Rushi Bhatt. 2012. Recommendations to boost content spread in social networks. In WWW. ACM 529--538.","DOI":"10.1145\/2187836.2187908"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Wei Chen Chi Wang and Yajun Wang. 2010. Scalable influence maximization for prevalent viral marketing in large-scale social networks. In KDD. ACM 1029--1038.","DOI":"10.1145\/1835804.1835934"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Wei Chen Yajun Wang and Siyu Yang. 2009. Efficient influence maximization in social networks. In KDD. ACM 199--208.","DOI":"10.1145\/1557019.1557047"},{"key":"e_1_2_1_10_1","volume-title":"Scalable Influence Maximization in Social Networks under the Linear Threshold Model","author":"Chen Wei","unstructured":"Wei Chen, Yifei Yuan, and Li Zhang. 2010. Scalable Influence Maximization in Social Networks under the Linear Threshold Model. In ICDM. IEEE Computer Society, 88--97."},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Suqi Cheng Huawei Shen Junming Huang Wei Chen and Xueqi Cheng. 2014. IMRank: influence maximization via finding self-consistent ranking. In SIGIR. ACM 475--484.","DOI":"10.1145\/2600428.2609592"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Suqi Cheng Huawei Shen Junming Huang Guoqing Zhang and Xueqi Cheng. 2013. StaticGreedy: solving the scalability-accuracy dilemma in influence maximization. In CIKM. ACM 509--518.","DOI":"10.1145\/2505515.2505541"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2006.10129115"},{"key":"e_1_2_1_14_1","volume-title":"Lakshmanan","author":"Goyal Amit","year":"2011","unstructured":"Amit Goyal, Wei Lu, and Laks V. S. Lakshmanan. 2011. SIMPATH: An Efficient Algorithm for Influence Maximization under the Linear Threshold Model. In ICDM. IEEE Computer Society, 211--220."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/3611479.3611490"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/3099622.3099623"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/3565816.3565821"},{"key":"e_1_2_1_18_1","volume-title":"IRIE: Scalable and Robust Influence Maximization in Social Networks","author":"Jung Kyomin","year":"2012","unstructured":"Kyomin Jung, Wooram Heo, and Wei Chen. 2012. IRIE: Scalable and Robust Influence Maximization in Social Networks. In ICDM. IEEE Computer Society, 918--923."},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"David Kempe Jon M. Kleinberg and \u00c9va Tardos. 2003. Maximizing the spread of influence through a social network. In KDD. ACM 137--146.","DOI":"10.1145\/956750.956769"},{"key":"e_1_2_1_20_1","unstructured":"Elias Boutros Khalil Bistra Dilkina and Le Song. 2014. Scalable diffusion-aware optimization of network topology. In KDD. ACM 1226--1235."},{"key":"e_1_2_1_21_1","volume-title":"CIKM. ACM","author":"Khan Arijit","year":"2016","unstructured":"Arijit Khan. 2016. Towards Time-Discounted Influence Maximization. In CIKM. ACM, 1873--1876."},{"key":"e_1_2_1_22_1","volume-title":"PRICAI (Lecture Notes in Computer Science)","author":"Kimura Masahiro","unstructured":"Masahiro Kimura, Kazumi Saito, and Hiroshi Motoda. 2008. Solving the Contamination Minimization Problem on Networks for the Linear Threshold Model. In PRICAI (Lecture Notes in Computer Science), Vol. 5351. Springer, 977--984."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/357062.357071"},{"key":"e_1_2_1_24_1","volume-title":"SIGMOD Conference. ACM, 87--98","author":"Li Guoliang","year":"2014","unstructured":"Guoliang Li, Shuo Chen, Jianhua Feng, Kian-Lee Tan, and Wen-Syan Li. 2014. Efficient location-aware influence maximization. In SIGMOD Conference. ACM, 87--98."},{"key":"e_1_2_1_25_1","volume-title":"Time Constrained Influence Maximization in Social Networks","author":"Liu Bo","unstructured":"Bo Liu, Gao Cong, Dong Xu, and Yifeng Zeng. 2012. Time Constrained Influence Maximization in Social Networks. In ICDM. IEEE Computer Society, 439--448."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/362835.362838"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850578.2850581"},{"key":"e_1_2_1_28_1","volume-title":"Swine flu: Twitter's power to misinform. Foreign policy","author":"Morozov Evgeny","year":"2009","unstructured":"Evgeny Morozov. 2009. Swine flu: Twitter's power to misinform. Foreign policy (2009)."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"e_1_2_1_30_1","volume-title":"Stop-and-Stare: Optimal Sampling Algorithms for Viral Marketing in Billion-scale Networks. In SIGMOD Conference. ACM, 695--710","author":"Nguyen Hung T.","unstructured":"Hung T. Nguyen, My T. Thai, and Thang N. Dinh. 2016. Stop-and-Stare: Optimal Sampling Algorithms for Viral Marketing in Billion-scale Networks. In SIGMOD Conference. ACM, 695--710."},{"key":"e_1_2_1_31_1","volume-title":"Fast and Accurate Influence Maximization on Large Networks with Pruned Monte-Carlo Simulations","author":"Ohsaka Naoto","unstructured":"Naoto Ohsaka, Takuya Akiba, Yuichi Yoshida, and Ken-ichi Kawarabayashi. 2014. Fast and Accurate Influence Maximization on Large Networks with Pruned Monte-Carlo Simulations. In AAAI. AAAI Press, 138--144."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/3547305.3547324"},{"key":"e_1_2_1_33_1","volume-title":"Online Processing Algorithms for Influence Maximization. In SIGMOD Conference. ACM, 991--1005","author":"Tang Jing","year":"2018","unstructured":"Jing Tang, Xueyan Tang, Xiaokui Xiao, and Junsong Yuan. 2018. Online Processing Algorithms for Influence Maximization. In SIGMOD Conference. ACM, 991--1005."},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Jing Tang Xueyan Tang and Junsong Yuan. 2017. Influence Maximization Meets Efficiency and Effectiveness: A Hop-Based Approach. In ASONAM. ACM 64--71.","DOI":"10.1145\/3110025.3110041"},{"key":"e_1_2_1_35_1","first-page":"1","article-title":"An efficient and effective hop-based approach for influence maximization in social networks","volume":"8","author":"Tang Jing","year":"2018","unstructured":"Jing Tang, Xueyan Tang, and Junsong Yuan. 2018. An efficient and effective hop-based approach for influence maximization in social networks. Social Network Analysis and Mining 8 (2018), 1--19.","journal-title":"Social Network Analysis and Mining"},{"key":"e_1_2_1_36_1","volume-title":"Influence Maximization in Near-Linear Time: A Martingale Approach. In SIGMOD Conference. ACM, 1539--1554","author":"Tang Youze","year":"2015","unstructured":"Youze Tang, Yanchen Shi, and Xiaokui Xiao. 2015. Influence Maximization in Near-Linear Time: A Martingale Approach. In SIGMOD Conference. ACM, 1539--1554."},{"key":"e_1_2_1_37_1","volume-title":"SIGMOD Conference. ACM, 75--86","author":"Tang Youze","year":"2014","unstructured":"Youze Tang, Xiaokui Xiao, and Yanchen Shi. 2014. Influence maximization: near-optimal time complexity meets practical efficiency. In SIGMOD Conference. ACM, 75--86."},{"key":"e_1_2_1_38_1","volume-title":"Beyond Uniform Reverse Sampling: A Hybrid Sampling Technique for Misinformation Prevention","author":"Tong Guangmo Amo","unstructured":"Guangmo Amo Tong and Ding-Zhu Du. 2019. Beyond Uniform Reverse Sampling: A Hybrid Sampling Technique for Misinformation Prevention. In INFOCOM. IEEE, 1711--1719."},{"key":"e_1_2_1_39_1","volume-title":"An efficient randomized algorithm for rumor blocking in online social networks","author":"Tong Guangmo Amo","unstructured":"Guangmo Amo 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. In INFOCOM. IEEE, 1--9."},{"key":"e_1_2_1_40_1","volume-title":"Efficient Influence Minimization via Node Blocking. arXiv preprint arXiv:2405.12871","author":"Wang Jinghao","year":"2024","unstructured":"Jinghao Wang, Yanping Wu, Xiaoyang Wang, Ying Zhang, Lu Qin, Wenjie Zhang, and Xuemin Lin. 2024. Efficient Influence Minimization via Node Blocking. arXiv preprint arXiv:2405.12871 (2024)."},{"key":"e_1_2_1_42_1","volume-title":"Distance-aware influence maximization in geo-social network","author":"Wang Xiaoyang","unstructured":"Xiaoyang Wang, Ying Zhang, Wenjie Zhang, and Xuemin Lin. 2016. Distance-aware influence maximization in geo-social network. In ICDE. IEEE Computer Society, 1--12."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2633472"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2624734"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2740284"},{"key":"e_1_2_1_46_1","volume-title":"Minimizing the Influence of Misinformation via Vertex Blocking","author":"Xie Jiadong","unstructured":"Jiadong Xie, Fan Zhang, Kai Wang, Xuemin Lin, and Wenjie Zhang. 2023. Minimizing the Influence of Misinformation via Vertex Blocking. In ICDE. IEEE, 789--801."},{"key":"e_1_2_1_47_1","first-page":"1088","article-title":"2-hop+ Sampling: Efficient and Effective Influence Estimation","volume":"35","author":"Zhu Yuqing","year":"2023","unstructured":"Yuqing Zhu, Jing Tang, Xueyan Tang, Sibo Wang, and Andrew Lim. 2023. 2-hop+ Sampling: Efficient and Effective Influence Estimation. IEEE Trans. Knowl. Data Eng. 35, 2 (2023), 1088--1103.","journal-title":"IEEE Trans. Knowl. Data Eng."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3675034.3675042","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,6]],"date-time":"2024-08-06T22:28:30Z","timestamp":1722983310000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3675034.3675042"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6]]},"references-count":46,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2024,6]]}},"alternative-id":["10.14778\/3675034.3675042"],"URL":"https:\/\/doi.org\/10.14778\/3675034.3675042","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,6]]},"assertion":[{"value":"2024-08-06","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}