{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T05:11:24Z","timestamp":1775538684420,"version":"3.50.1"},"reference-count":64,"publisher":"Association for Computing Machinery (ACM)","issue":"6","funder":[{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"publisher","award":["DP240101322, DP230101445, LP210301046, FT210100303"],"award-info":[{"award-number":["DP240101322, DP230101445, LP210301046, FT210100303"]}],"id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,12,4]]},"abstract":"<jats:p>Influence minimization (IMIN) aims to identify a set of nodes to be blocked, such that the expected number of nodes activated by the given seed set is minimized. It has many important applications, such as misinformation suppression, and has been extensively studied in the literature. Existing works for IMIN, however, neglect key temporal information in real-world scenarios. In this paper, we generalize IMIN and study the time-critical influence minimization (TCIM) problem, which aims to minimize the activation duration-aware influence spread of the seed set by a deadline via node blocking. We show that TCIM is NP-hard and APX-hard, and the objective function is non-submodular. To address the problem, we propose CBFM, an efficient and effective algorithm that provides \u03c4(1-1\/e-\u03b5)-approximation with at least 1-3\u03b4 probability, where \u03c4 is a data-driven parameter, \u03b5 and \u03b4 are tunable error parameters. Novel concentration results are designed to facilitate the establishment of the approximation guarantee. Moreover, we show that CBFM can be extended to tackle the misinformation mitigation (MM) problem. The existing MM solution offers the approximation guarantee only under specific assumptions. Our extended approach is assumption-free yet still attains the same guarantee, thereby bridging the theoretical gap. Finally, we conduct extensive experiments on 11 datasets to validate the performance of proposed algorithms on TCIM, IMIN (a special case of TCIM), and MM problems. The results show that for TCIM, CBFM achieves up to four orders of magnitude speedup over the baseline; for IMIN, CBFM outperforms the state-of-the-art in terms of efficiency, approximation ratio, and memory usage. Moreover, for MM, our solution can be two orders of magnitude faster than the corresponding state-of-the-art.<\/jats:p>","DOI":"10.1145\/3769834","type":"journal-article","created":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T04:32:13Z","timestamp":1764995533000},"page":"1-27","source":"Crossref","is-referenced-by-count":0,"title":["Time-Critical Influence Minimization via Node Blocking"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-6488-6098","authenticated-orcid":false,"given":"Jinghao","family":"Wang","sequence":"first","affiliation":[{"name":"University of Technology Sydney, Sydney, Australia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8804-4208","authenticated-orcid":false,"given":"Yanping","family":"Wu","sequence":"additional","affiliation":[{"name":"University of Technology Sydney, Sydney, Australia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3554-3219","authenticated-orcid":false,"given":"Xiaoyang","family":"Wang","sequence":"additional","affiliation":[{"name":"The University of New South Wales, Sydney, Australia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2674-1638","authenticated-orcid":false,"given":"Ying","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of Technology Sydney, Sydney, Australia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6572-2600","authenticated-orcid":false,"given":"Wenjie","family":"Zhang","sequence":"additional","affiliation":[{"name":"The University of New South Wales, Sydney, Australia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6068-5062","authenticated-orcid":false,"given":"Lu","family":"Qin","sequence":"additional","affiliation":[{"name":"University of Technology Sydney, Sydney, Australia"}]}],"member":"320","published-online":{"date-parts":[[2025,12,5]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2025. https:\/\/github.com\/wjh0116\/TCIM."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.3386\/w23089"},{"key":"e_1_2_1_3_1","volume-title":"Topic-aware social influence propagation models. Knowledge and information systems 37","author":"Barbieri Nicola","year":"2013","unstructured":"Nicola Barbieri, Francesco Bonchi, and Giuseppe Manco. 2013. Topic-aware social influence propagation models. Knowledge and information systems 37 (2013), 555-584."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASONAM.2012.170"},{"key":"e_1_2_1_5_1","volume-title":"ICML (Proceedings of Machine Learning Research","volume":"507","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_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634144"},{"key":"e_1_2_1_7_1","first-page":"591","article-title":"Time-Critical Influence Maximization in Social Networks with Time-Delayed Diffusion Process","author":"Chen Wei","year":"2012","unstructured":"Wei Chen,Wei Lu, and Ning Zhang. 2012. Time-Critical Influence Maximization in Social Networks with Time-Delayed Diffusion Process. In AAAI. 591-598.","journal-title":"AAAI."},{"key":"e_1_2_1_8_1","first-page":"1029","article-title":"Scalable influence maximization for prevalent viral marketing in large-scale social networks","author":"Chen Wei","year":"2010","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.","journal-title":"KDD. ACM"},{"key":"e_1_2_1_9_1","first-page":"199","article-title":"Efficient influence maximization in social networks","author":"Chen Wei","year":"2009","unstructured":"Wei Chen, Yajun Wang, and Siyu Yang. 2009. Efficient influence maximization in social networks. In KDD. ACM, 199-208.","journal-title":"KDD. ACM"},{"key":"e_1_2_1_10_1","first-page":"88","article-title":"Scalable Influence Maximization in Social Networks under the Linear Threshold Model","author":"Chen Wei","year":"2010","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.","journal-title":"ICDM. IEEE Computer Society"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2006.10129115"},{"key":"e_1_2_1_12_1","volume-title":"Werneck","author":"Cohen Edith","year":"2014","unstructured":"Edith Cohen, Daniel Delling, Thomas Pajor, and Renato F. Werneck. 2014. Timed Influence: Computation and Maximization. CoRR abs\/1410.6976 (2014)."},{"key":"e_1_2_1_13_1","unstructured":"Kevin DeLuca. 2020. Spotlight on Texas: Record Breaking Early Vote Turnout. https:\/\/electionlab.mit.edu\/articles\/ spotlight-texas-record-breaking-early-vote-turnout"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/502512.502525"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13278-014-0214-4"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2896377.2901462"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.knosys.2020.106693"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2824253"},{"key":"e_1_2_1_19_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_20_1","volume-title":"Influence Maximization Revisited: Efficient Reverse Reachable Set Generation with Bound Tightened. In SIGMOD Conference. ACM, 2167-2181","author":"Guo Qintian","year":"2020","unstructured":"Qintian Guo, Sibo Wang, Zhewei Wei, and Ming Chen. 2020. Influence Maximization Revisited: Efficient Reverse Reachable Set Generation with Bound Tightened. In SIGMOD Conference. ACM, 2167-2181."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/3099622.3099623"},{"key":"e_1_2_1_22_1","volume-title":"Impact of human activity patterns on the dynamics of information diffusion. Physical review letters 103, 3","author":"Iribarren Jos\u00e9 Luis","year":"2009","unstructured":"Jos\u00e9 Luis Iribarren and Esteban Moro. 2009. Impact of human activity patterns on the dynamics of information diffusion. Physical review letters 103, 3 (2009), 038702."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.83.025102"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2983323.2983862"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/357062.357071"},{"key":"e_1_2_1_27_1","first-page":"1415","article-title":"Efficient Dynamic Attributed Graph Generation","author":"Li Fan","year":"2025","unstructured":"Fan Li, Xiaoyang Wang, Dawei Cheng, Cong Chen, Ying Zhang, and Xuemin Lin. 2025. Efficient Dynamic Attributed Graph Generation. In ICDE. IEEE, 1415-1428.","journal-title":"ICDE. IEEE"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2024.3409869"},{"key":"e_1_2_1_29_1","first-page":"439","article-title":"Time Constrained Influence Maximization in Social Networks","author":"Liu Bo","year":"2012","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.","journal-title":"ICDM. IEEE Computer Society"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2013.106"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850578.2850581"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSMC.2021.3098630"},{"key":"e_1_2_1_33_1","volume-title":"Long-form reading shows signs of life in our mobile news world","author":"Mitchell Amy","year":"2016","unstructured":"Amy Mitchell, Galen Stocking, and Katerina Eva Matsa. 2016. Long-form reading shows signs of life in our mobile news world. Pew Research Center 5, 05 (2016)."},{"key":"e_1_2_1_34_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_35_1","volume-title":"Vaccine hesitancy and exposure to misinformation: a survey analysis. Journal of general internal medicine","author":"Neely Stephen R","year":"2022","unstructured":"Stephen R Neely, Christina Eldredge, Robin Ersing, and Christa Remington. 2022. Vaccine hesitancy and exposure to misinformation: a survey analysis. Journal of general internal medicine (2022), 1-9."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"e_1_2_1_37_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_38_1","unstructured":"Queensland Health. 2024. 2025 Free influenza vaccination program for eligible Queenslanders. https: \/\/www.health.qld.gov.au\/clinical-practice\/guidelines-procedures\/diseases-infection\/immunisation\/serviceproviders\/ 2025-free-flu-vaccination-program"},{"key":"e_1_2_1_39_1","unstructured":"Revolt. 2020. How to Change Your Vote: All the Details. https:\/\/www.revolt.tv\/article\/how-to-change-your-vote-allthe-details"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/3547305.3547324"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.134"},{"key":"e_1_2_1_42_1","first-page":"760","article-title":"Scalable Adversarial Attack Algorithms on Influence Maximization","author":"Sun Lichao","year":"2023","unstructured":"Lichao Sun, Xiaobin Rui, and Wei Chen. 2023. Scalable Adversarial Attack Algorithms on Influence Maximization. In WSDM. ACM, 760-768.","journal-title":"WSDM. ACM"},{"key":"e_1_2_1_43_1","first-page":"4310","article-title":"Higher-Order Peak Decomposition","author":"Tan Xingyu","year":"2023","unstructured":"Xingyu Tan, Jingya Qian, Chen Chen, Sima Qing, YanpingWu, XiaoyangWang, andWenjie Zhang. 2023. Higher-Order Peak Decomposition. In CIKM. ACM, 4310-4314.","journal-title":"CIKM. ACM"},{"key":"e_1_2_1_44_1","first-page":"3505","article-title":"Paths-over-Graph","author":"Tan Xingyu","year":"2025","unstructured":"Xingyu Tan, Xiaoyang Wang, Qing Liu, Xiwei Xu, Xin Yuan, and Wenjie Zhang. 2025. Paths-over-Graph: Knowledge Graph Empowered Large Language Model Reasoning. In WWW. ACM, 3505-3522.","journal-title":"Knowledge Graph Empowered Large Language Model Reasoning. In WWW. ACM"},{"key":"e_1_2_1_45_1","volume-title":"Hydra: Structured Cross-Source Enhanced Large Language Model Reasoning. CoRR abs\/2505.17464","author":"Tan Xingyu","year":"2025","unstructured":"Xingyu Tan, Xiaoyang Wang, Qing Liu, Xiwei Xu, Xin Yuan, Liming Zhu, and Wenjie Zhang. 2025. Hydra: Structured Cross-Source Enhanced Large Language Model Reasoning. CoRR abs\/2505.17464 (2025)."},{"key":"e_1_2_1_46_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_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2723734"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2593670"},{"key":"e_1_2_1_49_1","volume-title":"The spread of true and false news online. science 359, 6380","author":"Vosoughi Soroush","year":"2018","unstructured":"Soroush Vosoughi, Deb Roy, and Sinan Aral. 2018. The spread of true and false news online. science 359, 6380 (2018), 1146-1151."},{"key":"e_1_2_1_50_1","first-page":"4673","article-title":"Effective Influence Maximization with Priority","author":"Wang Jinghao","year":"2025","unstructured":"Jinghao Wang, Yanping Wu, Xiaoyang Wang, Chen Chen, Ying Zhang, and Lu Qin. 2025. Effective Influence Maximization with Priority. In WWW. ACM, 4673-4683.","journal-title":"WWW. ACM"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.14778\/3675034.3675042"},{"key":"e_1_2_1_52_1","unstructured":"Senzhang Wang Xiaojian Zhao Yan Chen Zhoujun Li Kai Zhang and Jiali Xia. 2013. Negative Influence Minimizing by Blocking Nodes in Social Networks. In AAAI (Late-Breaking Developments) (AAAI Technical Report Vol. WS-13-17). AAAI."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2624734"},{"key":"e_1_2_1_54_1","volume-title":"How disinformation defined the 2024 election narrative. Brookings Institution (November","author":"West Darrell M.","year":"2024","unstructured":"Darrell M. West. 2024. How disinformation defined the 2024 election narrative. Brookings Institution (November 2024). https:\/\/www.brookings.edu\/articles\/how-disinformation-defined-the-2024-election-narrative\/"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.14778\/3681954.3681997"},{"key":"e_1_2_1_56_1","first-page":"3098","article-title":"Efficient Maximal Temporal Plex Enumeration","author":"Sun Renjie","year":"2024","unstructured":"YanpingWu, Renjie Sun, XiaoyangWang, Ying Zhang, Lu Qin,Wenjie Zhang, and Xuemin Lin. 2024. Efficient Maximal Temporal Plex Enumeration. In ICDE. IEEE, 3098-3110.","journal-title":"ICDE. IEEE"},{"key":"e_1_2_1_57_1","first-page":"734","article-title":"Targeted Filter Bubbles Mitigating via Edges Insertion. In WWW (Companion Volume)","author":"Wu Yanping","year":"2024","unstructured":"Yanping Wu, Jinghao Wang, Renjie Sun, Chen Chen, Xiaoyang Wang, and Ying Zhang. 2024. Targeted Filter Bubbles Mitigating via Edges Insertion. In WWW (Companion Volume). ACM, 734-737.","journal-title":"ACM"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11280-024-01235-w"},{"key":"e_1_2_1_59_1","first-page":"789","article-title":"Minimizing the Influence of Misinformation via Vertex Blocking","author":"Xie Jiadong","year":"2023","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.","journal-title":"ICDE. IEEE"},{"key":"e_1_2_1_60_1","volume-title":"andWenjie Zhang","author":"Xie Jiadong","year":"2025","unstructured":"Jiadong Xie, Fan Zhang, KaiWang, Jialu Liu, Xuemin Lin, andWenjie Zhang. 2025. Influence minimization via blocking strategies. INFORMS Journal on Computing (2025)."},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2023.121847"},{"key":"e_1_2_1_62_1","volume-title":"Graph is a Natural Regularization: Revisiting Vector Quantization for Graph Representation Learning. CoRR abs\/2508.06588","author":"Zhai Zian","year":"2025","unstructured":"Zian Zhai, Fan Li, Xingyu Tan, Xiaoyang Wang, and Wenjie Zhang. 2025. Graph is a Natural Regularization: Revisiting Vector Quantization for Graph Representation Learning. CoRR abs\/2508.06588 (2025)."},{"key":"e_1_2_1_63_1","volume-title":"Adapting Unsigned Graph Neural Networks for Signed Graphs: A Few-Shot Prompt Tuning Approach. CoRR abs\/2412.12155","author":"Zhai Zian","year":"2024","unstructured":"Zian Zhai, Sima Qing, Xiaoyang Wang, and Wenjie Zhang. 2024. Adapting Unsigned Graph Neural Networks for Signed Graphs: A Few-Shot Prompt Tuning Approach. CoRR abs\/2412.12155 (2024)."},{"key":"e_1_2_1_64_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 ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3769834","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T04:29:44Z","timestamp":1775536184000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3769834"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,4]]},"references-count":64,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,12,4]]}},"alternative-id":["10.1145\/3769834"],"URL":"https:\/\/doi.org\/10.1145\/3769834","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,4]]}}}