{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T14:46:27Z","timestamp":1773153987946,"version":"3.50.1"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,2]]},"abstract":"<jats:p>Competitive viral marketing considers the product competition of multiple companies, where each user may adopt one product and propagate the product to other users. Existing studies focus on a traditional seeding strategy where a company only selects seeds from the users with no adopted product to maximize its influence (i.e., the number of users who will adopt its product). However, influential users are often rare, and the gain from traditional seeding will degrade as the number of seeds increases. Therefore, in this paper, we study the promising<jats:italic>countering<\/jats:italic>strategy which is to counter some users who initially use other products s.t. they will turn to adopting the target product and recommending it to others.<\/jats:p><jats:p>We propose the problem of<jats:italic>influence countering<\/jats:italic>: given a graph, a budget<jats:italic>b<\/jats:italic>, a target company<jats:italic>C<jats:sub>t<\/jats:sub><\/jats:italic>, and a set<jats:italic>S<\/jats:italic>of the seeds adopting different companies (where each seed adopts one company), we counter<jats:italic>b<\/jats:italic>users in<jats:italic>S<\/jats:italic>who do not adopt<jats:italic>C<jats:sub>t<\/jats:sub><\/jats:italic>to turn to adopt<jats:italic>C<jats:sub>t<\/jats:sub><\/jats:italic>s.t. the expected number of users who eventually adopt<jats:italic>C<jats:sub>t<\/jats:sub><\/jats:italic>in the influence diffusion is maximized. Following existing studies, we formalize the diffusion process by the Multi-Campaigner Independent Cascade model. We prove the influence countering problem is #P-complete and its influence computation is #P-hard. Then, we propose two novel algorithms<jats:italic>MIC<\/jats:italic>and<jats:italic>MIC<\/jats:italic><jats:sup>+<\/jats:sup>to address the problem. In general,<jats:italic>MIC<\/jats:italic>estimates seed influence by its empirical average influence in multiple graph samplings, while<jats:italic>MIC<\/jats:italic><jats:sup>+<\/jats:sup>improves<jats:italic>MIC<\/jats:italic>by reducing the cost of influence estimation and the required number of samples. Given pre-set<jats:italic>\u03b5<\/jats:italic>and<jats:italic>l<\/jats:italic>, both algorithms return a (1 -<jats:italic>\u03b5<\/jats:italic>)-approximate solution with at least 1 -<jats:italic>n<\/jats:italic><jats:sup>-<jats:italic>l<\/jats:italic><\/jats:sup>probability. We also design an index for<jats:italic>MIC<\/jats:italic><jats:sup>+<\/jats:sup>to efficiently process graphs that are frequently updated. The experiments on 8 real-world datasets show that our algorithms are efficient in practice while offering strong result quality.<\/jats:p>","DOI":"10.14778\/3648160.3648171","type":"journal-article","created":{"date-parts":[[2024,5,3]],"date-time":"2024-05-03T21:52:53Z","timestamp":1714773173000},"page":"1297-1309","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Influence Maximization via Vertex Countering"],"prefix":"10.14778","volume":"17","author":[{"given":"Jiadong","family":"Xie","sequence":"first","affiliation":[{"name":"Guangzhou University, Chinese University of Hong Kong"}]},{"given":"Zehua","family":"Chen","sequence":"additional","affiliation":[{"name":"Guangzhou University"}]},{"given":"Deming","family":"Chu","sequence":"additional","affiliation":[{"name":"University of New South Wale"}]},{"given":"Fan","family":"Zhang","sequence":"additional","affiliation":[{"name":"Guangzhou University"}]},{"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[{"name":"ACEM, Shanghai Jiao Tong University"}]},{"given":"Zhihong","family":"Tian","sequence":"additional","affiliation":[{"name":"Guangzhou University"}]}],"member":"320","published-online":{"date-parts":[[2024,5,3]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Hamid Ahmadi Beni, Asgarali Bouyer, and Afsaneh Fatemi.","author":"Aghaee Zahra","year":"2021","unstructured":"Zahra Aghaee, Mohammad Mahdi Ghasemi, Hamid Ahmadi Beni, Asgarali Bouyer, and Afsaneh Fatemi. 2021. A survey on meta-heuristic algorithms for the influence maximization problem in the social networks. Computing (2021), 2437--2477."},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Akhil Arora Sainyam Galhotra and Sayan Ranu. 2017. Debunking the Myths of Influence Maximization: An In-Depth Benchmarking Study. In SIGMOD. ACM 651--666.","DOI":"10.1145\/3218967"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Suman Banerjee Mamata Jenamani and Dilip Kumar Pratihar. 2020. A survey on influence maximization in a social network. Knowl. Inf. Syst. (2020) 3417--3455.","DOI":"10.1007\/s10115-020-01461-4"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-021-00679-0"},{"key":"e_1_2_1_5_1","volume-title":"Third International Workshop, WINE (Lecture Notes in Computer Science","volume":"311","author":"Bharathi Shishir","year":"2007","unstructured":"Shishir Bharathi, David Kempe, and Mahyar Salek. 2007. Competitive Influence Maximization in Social Networks. In Internet and Network Economics, Third International Workshop, WINE (Lecture Notes in Computer Science, Vol. 4858). Springer, 306--311."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSC.2016.2619688"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Christian Borgs Michael Brautbar Jennifer T. Chayes and Brendan Lucier. 2014. Maximizing Social Influence in Nearly Optimal Time. In SODA. 946--957.","DOI":"10.1137\/1.9781611973402.70"},{"key":"e_1_2_1_8_1","volume-title":"WINE (Lecture Notes in Computer Science","volume":"550","author":"Borodin Allan","year":"2010","unstructured":"Allan Borodin, Yuval Filmus, and Joel Oren. 2010. Threshold Models for Competitive Influence in Social Networks. In Internet and Network Economics - 6th International Workshop, WINE (Lecture Notes in Computer Science, Vol. 6484). Springer, 539--550."},{"key":"e_1_2_1_9_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. 665--674.","DOI":"10.1145\/1963405.1963499"},{"key":"e_1_2_1_10_1","volume-title":"ICEC (ACM International Conference Proceeding Series","volume":"360","author":"Carnes Tim","year":"2007","unstructured":"Tim Carnes, Chandrashekhar Nagarajan, Stefan M. Wild, and Anke van Zuylen. 2007. Maximizing influence in a competitive social network: a follower's perspective. In ICEC (ACM International Conference Proceeding Series, Vol. 258). ACM, 351--360."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735703.2735706"},{"key":"e_1_2_1_12_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_13_1","volume-title":"Domingos and Matthew Richardson","author":"Pedro","year":"2001","unstructured":"Pedro M. Domingos and Matthew Richardson. 2001. Mining the network value of customers. In KDD. ACM, 57--66."},{"key":"e_1_2_1_14_1","volume-title":"Kearns","author":"Goyal Sanjeev","year":"2012","unstructured":"Sanjeev Goyal and Michael J. Kearns. 2012. Competitive contagion in networks. In STOC. ACM, 759--774."},{"key":"e_1_2_1_15_1","volume-title":"Influence Maximization in Trajectory Databases","author":"Guo Long","unstructured":"Long Guo, Dongxiang Zhang, Gao Cong, Wei Wu, and Kian-Lee Tan. 2017. Influence Maximization in Trajectory Databases. In ICDE. IEEE Computer Society, 27--28."},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Qintian Guo Sibo Wang Zhewei Wei and Ming Chen. 2020. Influence Maximization Revisited: Efficient Reverse Reachable Set Generation with Bound Tightened. In SIGMOD. 2167--2181.","DOI":"10.1145\/3318464.3389740"},{"key":"e_1_2_1_17_1","volume-title":"WINE (Lecture Notes in Computer Science","volume":"248","author":"He Xinran","year":"2013","unstructured":"Xinran He and David Kempe. 2013. Price of Anarchy for the N-Player Competitive Cascade Game with Submodular Activation Functions. In WINE (Lecture Notes in Computer Science, Vol. 8289). Springer, 232--248."},{"key":"e_1_2_1_18_1","volume-title":"Influence Blocking Maximization in Social Networks under the Competitive Linear Threshold Model","author":"He Xinran","unstructured":"Xinran He, Guojie Song, Wei Chen, and Qingye Jiang. 2012. Influence Blocking Maximization in Social Networks under the Competitive Linear Threshold Model. In SIAM. SIAM \/ Omnipress, 463--474."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/3099622.3099623"},{"key":"e_1_2_1_20_1","volume-title":"IRIE: Scalable and Robust Influence Maximization in Social Networks. In ICDM. 918--923.","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. 918--923."},{"key":"e_1_2_1_21_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_22_1","volume-title":"Revenue maximization by viral marketing: A social network host's perspective","author":"Khan Arijit","unstructured":"Arijit Khan, Benjamin Zehnder, and Donald Kossmann. 2016. Revenue maximization by viral marketing: A social network host's perspective. In ICDE. IEEE Computer Society, 37--48."},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Ravi Kumar Jasmine Novak and Andrew Tomkins. 2006. Structure and evolution of online social networks. In KDD. ACM 611--617.","DOI":"10.1145\/1150402.1150476"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Jure Leskovec Jon M. Kleinberg and Christos Faloutsos. 2005. Graphs over time: densification laws shrinking diameters and possible explanations. In KDD. ACM 177--187.","DOI":"10.1145\/1081870.1081893"},{"key":"e_1_2_1_25_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Guoliang Li Shuo Chen Jianhua Feng Kian-Lee Tan and Wen-Syan Li. 2014. Efficient location-aware influence maximization. In SIGMOD. ACM 87--98.","DOI":"10.1145\/2588555.2588561"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Hui Li Sourav S. Bhowmick Jiangtao Cui Yunjun Gao and Jianfeng Ma. 2015. GetReal: Towards Realistic Selection of Influence Maximization Strategies in Competitive Networks. In SIGMOD. ACM 1525--1537.","DOI":"10.1145\/2723372.2723710"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2807843"},{"key":"e_1_2_1_29_1","volume-title":"Boosting Nodes for Improving the Spread of Influence. CoRR abs\/1609.03478","author":"Liontis Konstantinos","year":"2016","unstructured":"Konstantinos Liontis and Evaggelia Pitoura. 2016. Boosting Nodes for Improving the Spread of Influence. CoRR abs\/1609.03478 (2016)."},{"key":"e_1_2_1_30_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_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2013.106"},{"key":"e_1_2_1_32_1","volume-title":"Lakshmanan","author":"Lu Wei","year":"2013","unstructured":"Wei Lu, Francesco Bonchi, Amit Goyal, and Laks V. S. Lakshmanan. 2013. The bang for the buck: fair competitive viral marketing from the host perspective. In KDD. ACM, 928--936."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850578.2850581"},{"key":"e_1_2_1_34_1","volume-title":"Randomized Algorithms","author":"Motwani Rajeev","unstructured":"Rajeev Motwani and Prabhakar Raghavan. 1995. Randomized Algorithms. Cambridge University Press."},{"key":"e_1_2_1_35_1","volume-title":"Thai","author":"Nguyen Hung T.","year":"2018","unstructured":"Hung T. Nguyen, Thang N. Dinh, and My T. Thai. 2018. Revisiting of 'Revisiting the Stop-and-Stare Algorithms for Influence Maximization'. In CSoNet (Lecture Notes in Computer Science, Vol. 11280). Springer, 273--285."},{"key":"e_1_2_1_36_1","volume-title":"Dinh","author":"Nguyen Hung T.","year":"2016","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. ACM, 695--710."},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Naoto Ohsaka. 2020. The Solution Distribution of Influence Maximization: A High-level Experimental Study on Three Algorithmic Approaches. In SIGMOD. ACM 2151--2166.","DOI":"10.1145\/3318464.3380564"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/2994509.2994525"},{"key":"e_1_2_1_39_1","volume-title":"NeurIPS","author":"Peng Binghui","year":"2021","unstructured":"Binghui Peng. 2021. Dynamic influence maximization. In NeurIPS 2021. 10718--10731."},{"key":"e_1_2_1_40_1","doi-asserted-by":"crossref","unstructured":"Jing Tang Xueyan Tang Xiaokui Xiao and Junsong Yuan. 2018. Online Processing Algorithms for Influence Maximization. In SIGMOD. ACM 991--1005.","DOI":"10.1145\/3183713.3183749"},{"key":"e_1_2_1_41_1","doi-asserted-by":"crossref","unstructured":"Youze Tang Yanchen Shi and Xiaokui Xiao. 2015. Influence Maximization in Near-Linear Time: A Martingale Approach. In SIGMOD. ACM 1539--1554.","DOI":"10.1145\/2723372.2723734"},{"key":"e_1_2_1_42_1","doi-asserted-by":"crossref","unstructured":"Youze Tang Xiaokui Xiao and Yanchen Shi. 2014. Influence maximization: near-optimal time complexity meets practical efficiency. In SIGMOD. ACM 75--86.","DOI":"10.1145\/2588555.2593670"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/3450980.3450981"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208032"},{"key":"e_1_2_1_45_1","volume-title":"ICML (Proceedings of Machine Learning Research","volume":"3539","author":"Vaswani Sharan","year":"2017","unstructured":"Sharan Vaswani, Branislav Kveton, Zheng Wen, Mohammad Ghavamzadeh, Laks V. S. Lakshmanan, and Mark Schmidt. 2017. Model-Independent Online Learning for Influence Maximization. In ICML (Proceedings of Machine Learning Research, Vol. 70). PMLR, 3530--3539."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/3067421.3067429"},{"key":"e_1_2_1_47_1","article-title":"Location-aware Influence Maximization over Dynamic Social Streams","volume":"36","author":"Wang Yanhao","year":"2018","unstructured":"Yanhao Wang, Yuchen Li, Ju Fan, and Kian-Lee Tan. 2018. Location-aware Influence Maximization over Dynamic Social Streams. ACM Trans. Inf. Syst. 36, 4 (2018), 43:1--43:35.","journal-title":"ACM Trans. Inf. Syst."},{"key":"e_1_2_1_48_1","volume-title":"39th IEEE International Conference on Data Engineering, ICDE","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 39th IEEE International Conference on Data Engineering, ICDE 2023. IEEE, 789--801."},{"key":"e_1_2_1_49_1","volume-title":"Influence Minimization via Blocking Strategies. CoRR abs\/2312.17488","author":"Xie Jiadong","year":"2023","unstructured":"Jiadong Xie, Fan Zhang, Kai Wang, Jialu Liu, Xuemin Lin, and Wenjie Zhang. 2023. Influence Minimization via Blocking Strategies. CoRR abs\/2312.17488 (2023). arXiv:2312.17488"},{"key":"e_1_2_1_50_1","volume-title":"DynaDiffuse: A Dynamic Diffusion Model for Continuous Time Constrained Influence Maximization","author":"Xie Miao","unstructured":"Miao Xie, Qiusong Yang, Qing Wang, Gao Cong, and Gerard de Melo. 2015. DynaDiffuse: A Dynamic Diffusion Model for Continuous Time Constrained Influence Maximization. In AAAI. AAAI Press, 346--352."},{"key":"e_1_2_1_51_1","doi-asserted-by":"crossref","unstructured":"Yipeng Zhang Yuchen Li Zhifeng Bao Baihua Zheng and H. V. Jagadish. 2021. Minimizing the Regret of an Influence Provider. In SIGMOD. ACM 2115--2127.","DOI":"10.1145\/3448016.3457257"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.14778\/3489496.3489514"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3648160.3648171","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,18]],"date-time":"2024-11-18T01:01:28Z","timestamp":1731891688000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3648160.3648171"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2]]},"references-count":52,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,2]]}},"alternative-id":["10.14778\/3648160.3648171"],"URL":"https:\/\/doi.org\/10.14778\/3648160.3648171","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,2]]},"assertion":[{"value":"2024-05-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}