{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T14:43:45Z","timestamp":1781621025346,"version":"3.54.5"},"reference-count":58,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,10]]},"abstract":"<jats:p>\n            Influence maximization (IM) is a classic problem that aims to identify a small group of critical individuals, known as seeds, who can influence the largest number of users in a social network through word-of-mouth. This problem finds important applications including viral marketing, infection detection, and misinformation containment. The conventional IM problem is typically studied with the oversimplified goal of selecting a\n            <jats:italic>single<\/jats:italic>\n            seed set. Many real-world scenarios call for\n            <jats:italic>multiple<\/jats:italic>\n            sets of seeds, particularly on social media platforms where various viral marketing campaigns need different sets of seeds to propagate effectively. To this end, previous works have formulated various IM variants, central to which is the requirement of multiple seed sets, naturally modeled as a matroid constraint. However, the current best-known solutions for these variants either offer a weak (1\/2 -\n            <jats:italic>\u03b5<\/jats:italic>\n            )-approximation, or offer a (1 - 1\/\n            <jats:italic>e - \u03b5<\/jats:italic>\n            )-approximation algorithm that is very expensive. We propose an efficient seed selection method called AMP, an algorithm with a (1 - 1\/\n            <jats:italic>e<\/jats:italic>\n            -\n            <jats:italic>\u03b5<\/jats:italic>\n            )-approximation guarantee for this family of IM variants. To further improve efficiency, we also devise a fast implementation, called RAMP. We extensively evaluate the performance of our proposal against 6 competitors across 4 IM variants and on 7 real-world networks, demonstrating that our proposal outperforms all competitors in terms of result quality, running time, and memory usage. We have also deployed RAMP in a real industry strength application involving online gaming, where we show that our deployed solution significantly improves upon the baselines.\n          <\/jats:p>","DOI":"10.14778\/3705829.3705833","type":"journal-article","created":{"date-parts":[[2025,2,28]],"date-time":"2025-02-28T23:21:06Z","timestamp":1740784866000},"page":"117-129","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Efficient and Effective Algorithms for A Family of Influence Maximization Problems with A Matroid Constraint"],"prefix":"10.14778","volume":"18","author":[{"given":"Yiqian","family":"Huang","sequence":"first","affiliation":[{"name":"National University of Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shiqi","family":"Zhang","sequence":"additional","affiliation":[{"name":"National University of Singapore, PyroWis AI"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Laks V. S.","family":"Lakshmanan","sequence":"additional","affiliation":[{"name":"University of British Columbia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wenqing","family":"Lin","sequence":"additional","affiliation":[{"name":"Tencent"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiaokui","family":"Xiao","sequence":"additional","affiliation":[{"name":"National University of Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bo","family":"Tang","sequence":"additional","affiliation":[{"name":"Southern University of Science and Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,2,28]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:JOCO.0000038913.96607.c2"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137635"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Lars Backstrom Paolo Boldi Marco Rosa Johan Ugander and Sebastiano Vigna. 2012. Four degrees of separation. In Web Science. 33--42.","DOI":"10.1145\/2380718.2380723"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Ashwinkumar Badanidiyuru and Jan Vondr\u00e5k. 2014. Fast algorithms for maximizing submodular functions. In SODA. 1497--1514.","DOI":"10.1137\/1.9781611973402.110"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Ruben Becker Gianlorenzo d'Angelo and Hugo Gilbert. 2021. Influence Maximization With Co-Existing Seeds. In CIKM. 100--109.","DOI":"10.1145\/3459637.3482439"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/3397230.3397244"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Christian Borgs Michael Brautbar Jennifer 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","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2016.0809"},{"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","unstructured":"ByteDance. 2023. Recruitment-based Campaign in the Document of Douyin Xingtu Platform. https:\/\/www.xingtu.cn\/help-center\/demander\/126583."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/080733991"},{"key":"e_1_2_1_12_1","volume-title":"International Workshop on Frontiers in Algorithmics. 37--48","author":"Hubert Chan T-H","year":"2020","unstructured":"T-H Hubert Chan, Li Ning, and Yong Zhang. 2020. Influence maximization under the non-progressive linear threshold model. In International Workshop on Frontiers in Algorithmics. 37--48."},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Chandra Chekuri Jan Vondr\u00e5k and Rico Zenklusen. 2010. Dependent randomized rounding via exchange properties of combinatorial structures. In FOCS. 575--584.","DOI":"10.1109\/FOCS.2010.60"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Tianqi Chen and Carlos Guestrin. 2016. XGBoost: A Scalable Tree Boosting System. In SIGKDD. 785--794.","DOI":"10.1145\/2939672.2939785"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCSS.2020.2998777"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Pedro Domingos and Matt Richardson. 2001. Mining the network value of customers. In SIGKDD. 57--66.","DOI":"10.1145\/502512.502525"},{"key":"e_1_2_1_17_1","first-page":"1","article-title":"Scalable Influence Maximization for Multiple Products in Continuous-Time Diffusion Networks","volume":"18","author":"Du Nan","year":"2017","unstructured":"Nan Du, Yingyu Liang, Maria-Florina Balcan, Manuel Gomez-Rodriguez, Hongyuan Zha, and Le Song. 2017. Scalable Influence Maximization for Multiple Products in Continuous-Time Diffusion Networks. J. Mach. Learn. Res. 18, 2 (2017), 1--45.","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584082"},{"key":"e_1_2_1_19_1","unstructured":"Marwa El Halabi Slobodan Mitrovi\u0107 Ashkan Norouzi-Fard Jakab Tardos and Jakub M Tarnawski. 2020. Fairness in Streaming Submodular Maximization: Algorithms and Hardness. In NeurIPS. 13609--13622."},{"key":"e_1_2_1_20_1","first-page":"1","article-title":"Towards Nearly-Linear Time Algorithms for Submodular Maximization with a Matroid Constraint","volume":"54","author":"Ene Alina","year":"2019","unstructured":"Alina Ene and Huy L. Nguyen. 2019. Towards Nearly-Linear Time Algorithms for Submodular Maximization with a Matroid Constraint. In ICALP. 54:1--54:14.","journal-title":"ICALP."},{"key":"e_1_2_1_21_1","unstructured":"Ocean Engine. 2022. ByteDance Xingtu Creator Ecosystem Report. https:\/\/trendinsight.oceanengine.com\/arithmetic-report\/detail\/773."},{"key":"e_1_2_1_22_1","unstructured":"Ocean Engine. 2023. China Influencer Marketing with Douyin and Xingtu. https:\/\/www.oceanengine.io\/resource\/china-influencer-marketing-douyin-xingtu-tips-strategies."},{"key":"e_1_2_1_23_1","volume-title":"A case study of the pyramid scheme in China based on communication network. Physica A: Statistical Mechanics and its Applications 565","author":"Feng Pihu","year":"2021","unstructured":"Pihu Feng, Xin Lu, Zaiwu Gong, and Duoyong Sun. 2021. A case study of the pyramid scheme in China based on communication network. Physica A: Statistical Mechanics and its Applications 565 (2021), 125548."},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Marshall L Fisher George L Nemhauser and Laurence A Wolsey. 1978. An analysis of approximations for maximizing submodular set functions---II. In Polyhedral combinatorics. 73--87.","DOI":"10.1007\/BFb0121195"},{"key":"e_1_2_1_25_1","volume-title":"Talk of the network: A complex systems look at the underlying process of word-of-mouth. Marketing letters 12, 3","author":"Goldenberg Jacob","year":"2001","unstructured":"Jacob Goldenberg, Barak Libai, and Eitan Muller. 2001. Talk of the network: A complex systems look at the underlying process of word-of-mouth. Marketing letters 12, 3 (2001), 211--223."},{"key":"e_1_2_1_26_1","volume-title":"Threshold models of collective behavior. American journal of sociology 83, 6","author":"Granovetter Mark","year":"1978","unstructured":"Mark Granovetter. 1978. Threshold models of collective behavior. American journal of sociology 83, 6 (1978), 1420--1443."},{"key":"e_1_2_1_27_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_28_1","article-title":"Influence Maximization Revisited: Efficient Sampling with Bound Tightened","volume":"47","author":"Guo Qintian","year":"2022","unstructured":"Qintian Guo, Sibo Wang, Zhewei Wei, Wenqing Lin, and Jing Tang. 2022. Influence Maximization Revisited: Efficient Sampling with Bound Tightened. ACM Transactions on Database Systems 47, 3 (2022).","journal-title":"ACM Transactions on Database Systems"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Kai Han Benwei Wu Jing Tang Shuang Cui Cigdem Aslay and Laks VS Lakshmanan. 2021. Efficient and effective algorithms for revenue maximization in social advertising. In SIGMOD. 671--684.","DOI":"10.1145\/3448016.3459243"},{"key":"e_1_2_1_30_1","first-page":"1","article-title":"Faster Submodular Maximization for Several Classes of Matroids","volume":"74","author":"Henzinger Monika","year":"2023","unstructured":"Monika Henzinger, Paul Liu, Jan Vondr\u00e5k, and Da Wei Zheng. 2023. Faster Submodular Maximization for Several Classes of Matroids. In ICALP. 74:1--74:18.","journal-title":"ICALP."},{"key":"e_1_2_1_31_1","unstructured":"Yiqian Huang Shiqi Zhang Laks V. S. Lakshmanan Wenqing Lin Xiaokui Xiao and Bo Tang. 2024. Efficient and Effective Algorithms for A Family of Influence Maximization Problems with A Matroid Constraint [Technical Report]. arXiv:2410.16603 [cs.SI] https:\/\/arxiv.org\/abs\/2410.16603"},{"key":"e_1_2_1_32_1","volume-title":"Top Influencer Marketing Platforms for","author":"Hub Influencer Marketing","year":"2024","unstructured":"Influencer Marketing Hub. 2024. Top Influencer Marketing Platforms for April 2024. https:\/\/influencermarketinghub.com\/influencer-marketing-platforms."},{"key":"e_1_2_1_33_1","unstructured":"Instagram. 2022. Introducing Creator Marketplace Where Brands Can Discover Creators to Collaborate With. https:\/\/business.instagram.com\/blog\/creator-marketplace-discover-partnerships."},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","first-page":"426","DOI":"10.1108\/cpoib-10-2021-0088","article-title":"Money laundering as a transnational business phenomenon: a systematic review and future agenda","volume":"19","author":"Isolauri Emilia A","year":"2023","unstructured":"Emilia A Isolauri and Irfan Ameer. 2023. Money laundering as a transnational business phenomenon: a systematic review and future agenda. Critical Perspectives on International Business 19, 3 (2023), 426--468.","journal-title":"Critical Perspectives on International Business"},{"key":"e_1_2_1_35_1","volume-title":"Christophe Van den Bulte, and Thomas W Valente","author":"Iyengar Raghuram","year":"2011","unstructured":"Raghuram Iyengar, Christophe Van den Bulte, and Thomas W Valente. 2011. Opinion leadership and social contagion in new product diffusion. Marketing science 30, 2 (2011), 195--212."},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","unstructured":"David Kempe Jon Kleinberg and \u00c9va Tardos. 2003. Maximizing the spread of influence through a social network. In SIGKDD. 137--146.","DOI":"10.1145\/956750.956769"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Jure Leskovec Andreas Krause Carlos Guestrin Christos Faloutsos Jeanne VanBriesen and Natalie Glance. 2007. Cost-effective outbreak detection in networks. In SIGKDD. 420--429.","DOI":"10.1145\/1281192.1281239"},{"key":"e_1_2_1_38_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_39_1","first-page":"1884","article-title":"Automated influence maintenance in social networks: an agent-based approach","volume":"31","author":"Li Weihua","year":"2018","unstructured":"Weihua Li, Quan Bai, Minjie Zhang, and Tung Doan Nguyen. 2018. Automated influence maintenance in social networks: an agent-based approach. IEEE Transactions on Knowledge and Data Engineering 31, 10 (2018), 1884--1897.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2807843"},{"key":"e_1_2_1_41_1","first-page":"2","volume-title":"Proc. ACM Manag. Data 1","author":"Liao Hao","year":"2023","unstructured":"Hao Liao, Sheng Bi, Jiao Wu, Wei Zhang, Mingyang Zhou, Rui Mao, and Wei Chen. 2023. Popularity Ratio Maximization: Surpassing Competitors through Influence Propagation. Proc. ACM Manag. Data 1, 2 (2023)."},{"key":"e_1_2_1_42_1","volume-title":"Accelerated greedy algorithms for maximizing submodular set functions. Optimization Techniques","author":"Minoux Michel","year":"1978","unstructured":"Michel Minoux. 1978. Accelerated greedy algorithms for maximizing submodular set functions. Optimization Techniques (1978), 234--243."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915207"},{"key":"e_1_2_1_44_1","doi-asserted-by":"crossref","unstructured":"Martin Saveski Jean Pouget-Abadie Guillaume Saint-Jacques Weitao Duan Souvik Ghosh Ya Xu and Edoardo M Airoldi. 2017. Detecting network effects: Randomizing over randomized experiments. In SIGKDD. 1027--1035.","DOI":"10.1145\/3097983.3098192"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/3547305.3547324"},{"key":"e_1_2_1_46_1","doi-asserted-by":"crossref","unstructured":"Lichao Sun Weiran Huang Philip S Yu and Wei Chen. 2018. Multi-round influence maximization. In SIGKDD. 2249--2258.","DOI":"10.1145\/3219819.3220101"},{"key":"e_1_2_1_47_1","doi-asserted-by":"crossref","unstructured":"Lichao Sun Xiaobin Rui and Wei Chen. 2023. Scalable Adversarial Attack Algorithms on Influence Maximization. In WSDM. 760--768.","DOI":"10.1145\/3539597.3570416"},{"key":"e_1_2_1_48_1","doi-asserted-by":"crossref","unstructured":"Jing Tang Xueyan Tang Xiaokui Xiao and Junsong Yuan. 2018. Online processing algorithms for influence maximization. In SIGMOD. 991--1005.","DOI":"10.1145\/3183713.3183749"},{"key":"e_1_2_1_49_1","volume-title":"AAAI","volume":"32","author":"Tang Shaojie","year":"2018","unstructured":"Shaojie Tang. 2018. When social advertising meets viral marketing: Sequencing social advertisements for influence maximization. In AAAI, Vol. 32."},{"key":"e_1_2_1_50_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. 1539--1554.","DOI":"10.1145\/2723372.2723734"},{"key":"e_1_2_1_51_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. 75--86.","DOI":"10.1145\/2588555.2593670"},{"key":"e_1_2_1_52_1","unstructured":"Tiktok. 2023. 5 ways TikTok Creator Marketplace makes creator marketing easy. https:\/\/www.tiktok.com\/business\/en-US\/blog\/making-creator-marketing-easy\/."},{"key":"e_1_2_1_53_1","volume-title":"NeurIPS","volume":"31","author":"Tong Amo","year":"2018","unstructured":"Amo Tong, Ding-Zhu Du, and Weili Wu. 2018. On Misinformation Containment in Online Social Networks. In NeurIPS, Vol. 31."},{"key":"e_1_2_1_54_1","doi-asserted-by":"crossref","unstructured":"Alan Tsang Bryan Wilder Eric Rice Milind Tambe and Yair Zick. 2019. Group-Fairness in Influence Maximization. In IJCAI. 5997--6005.","DOI":"10.24963\/ijcai.2019\/831"},{"key":"e_1_2_1_55_1","unstructured":"Rajan Udwani. 2018. Multi-Objective Maximization of Monotone Submodular Functions with Cardinality Constraint. In NeurIPS. 9513--9524."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10796-014-9509-2"},{"key":"e_1_2_1_57_1","doi-asserted-by":"crossref","unstructured":"Shiqi Zhang Yiqian Huang Jiachen Sun Wenqing Lin Xiaokui Xiao and Bo Tang. 2023. Capacity Constrained Influence Maximization in Social Networks. In SIGKDD. 3376--3385.","DOI":"10.1145\/3580305.3599267"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.14778\/3401960.3401961"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3705829.3705833","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,28]],"date-time":"2025-02-28T23:24:49Z","timestamp":1740785089000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3705829.3705833"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10]]},"references-count":58,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,10]]}},"alternative-id":["10.14778\/3705829.3705833"],"URL":"https:\/\/doi.org\/10.14778\/3705829.3705833","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,10]]},"assertion":[{"value":"2025-02-28","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}