{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T16:44:47Z","timestamp":1780764287582,"version":"3.54.1"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2023,11,13]],"date-time":"2023-11-13T00:00:00Z","timestamp":1699833600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["No. U1936205"],"award-info":[{"award-number":["No. U1936205"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Hong Kong RGC CRF Grant","award":["No. C4158-20G"],"award-info":[{"award-number":["No. C4158-20G"]}]},{"name":"Hong Kong RGC GRF Grant","award":["No. 14217322"],"award-info":[{"award-number":["No. 14217322"]}]},{"name":"Hong Kong RGC ECS Grant","award":["No. 24203419"],"award-info":[{"award-number":["No. 24203419"]}]},{"name":"Hong Kong ITC ITF Grant","award":["No. MRP\/071\/20X"],"award-info":[{"award-number":["No. MRP\/071\/20X"]}]},{"name":"Hong Kong ITC RTH Grant","award":["No. PiH\/012\/22"],"award-info":[{"award-number":["No. PiH\/012\/22"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,11,13]]},"abstract":"<jats:p>Given a graph G, a cost associated with each node, and a budget B, the budgeted influence maximization (BIM) aims to find the optimal set S of seed nodes that maximizes the influence among all possible sets such that the total cost of nodes in S is no larger than B. Existing solutions mainly follow the non-adaptive idea, i.e., determining all the seeds before observing any actual diffusion. Due to the absence of actual diffusion information, they may result in unsatisfactory influence spread. Motivated by the limitation of existing solutions, in this paper, we make the first attempt to solve the BIM problem under the adaptive setting, where seed nodes are iteratively selected after observing the diffusion result of the previous seeds. We design the first practical algorithm which achieves an expected approximation guarantee by probabilistically adopting a cost-aware greedy idea or a single influential node. Further, we develop an optimized version to improve its practical performance in terms of influence spread.<\/jats:p>\n          <jats:p>Besides, the scalability issues of the adaptive IM-related problems still remain open. It is because they usually involve multiple rounds (e.g., equal to the number of seeds) and in each round, they have to construct sufficient new reverse-reachable set (RR-set) samples such that the claimed approximation guarantee can actually hold. However, this incurs prohibitive computation, imposing limitations on real applications. To solve this dilemma, we propose an incremental update approach. Specifically, it maintains extra construction information when building RR-sets, and then it can quickly correct a problematic RR-set from the very step where it is first affected. As a result, we recycle the RR-sets at a small computational cost, while still providing correctness guarantee. Finally, extensive experiments on large-scale real graphs demonstrate the superiority of our algorithms over baselines in terms of both influence spread and running time.<\/jats:p>","DOI":"10.1145\/3617328","type":"journal-article","created":{"date-parts":[[2023,11,13]],"date-time":"2023-11-13T22:28:39Z","timestamp":1699914519000},"page":"1-26","source":"Crossref","is-referenced-by-count":12,"title":["Efficient Algorithm for Budgeted Adaptive Influence Maximization: An Incremental RR-set Update Approach"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9581-9817","authenticated-orcid":false,"given":"Qintian","family":"Guo","sequence":"first","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5495-8500","authenticated-orcid":false,"given":"Chen","family":"Feng","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-3253-4661","authenticated-orcid":false,"given":"Fangyuan","family":"Zhang","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1892-6971","authenticated-orcid":false,"given":"Sibo","family":"Wang","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,11,13]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137635"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Ashwinkumar Badanidiyuru and Jan Vondr\u00e1 k. 2014. Fast algorithms for maximizing submodular functions. In SODA. 1497--1514.","DOI":"10.1137\/1.9781611973402.110"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/3436905.3436920"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Shishir Bharathi David Kempe and Mahyar Salek. 2007. Competitive influence maximization in social networks. In WINE. 306--311.","DOI":"10.1007\/978-3-540-77105-0_31"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/3397230.3397244"},{"key":"e_1_2_1_6_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_7_1","first-page":"164","article-title":"Adaptive multi-feature budgeted profit maximization in social networks","volume":"12","author":"Chen Tiantian","year":"2022","unstructured":"Tiantian Chen, Jianxiong Guo, and Weili Wu. 2022. Adaptive multi-feature budgeted profit maximization in social networks. SNAM, Vol. 12, 1 (2022), 164.","journal-title":"SNAM"},{"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 SIGKDD. 1029--1038.","DOI":"10.1145\/1835804.1835934"},{"key":"e_1_2_1_9_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_10_1","first-page":"2844","article-title":"Neighborhood matters: Influence maximization in social networks with limited access","volume":"34","author":"Feng Chen","year":"2020","unstructured":"Chen Feng, Luoyi Fu, Bo Jiang, Haisong Zhang, Xinbing Wang, Feilong Tang, and Guihai Chen. 2020. Neighborhood matters: Influence maximization in social networks with limited access. IEEE Trans. Knowl. Data Eng., Vol. 34, 6 (2020), 2844--2859.","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"e_1_2_1_11_1","unstructured":"Flaminjoy. 2022. Influencer Marketing Budgets. https:\/\/flaminjoy.com\/blog\/influencer-marketing-budget\/."},{"key":"e_1_2_1_12_1","unstructured":"Forbes. 2021. One In Four Influencers Bought Fake Followers. https:\/\/www.forbes.com\/sites\/forbestechcouncil\/2022\/09\/09\/new-study-one-in-four-influencers-bought-fake-followers\/'sh=3e3471056843."},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Sainyam Galhotra Akhil Arora and Shourya Roy. 2016. Holistic Influence Maximization: Combining Scalability and Efficiency with Opinion-Aware Models. In SIGMOD. 743--758.","DOI":"10.1145\/2882903.2882929"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/2208436.2208448"},{"key":"e_1_2_1_15_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_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3533817"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/3213880.3213883"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Kai Han Chaoting Xu Fei Gui Shaojie Tang He Huang and Jun Luo. 2018b. Discount allocation for revenue maximization in online social networks. In MobiHoc. 121--130.","DOI":"10.1145\/3209582.3209595"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Shuo Han Fuzhen Zhuang Qing He and Zhongzhi Shi. 2014. Balanced seed selection for budgeted influence maximization in social networks. In PAKDD. 65--77.","DOI":"10.1007\/978-3-319-06608-0_6"},{"key":"e_1_2_1_20_1","volume-title":"NeurIPS","volume":"29","author":"He Xinran","year":"2016","unstructured":"Xinran He, Ke Xu, David Kempe, and Yan Liu. 2016. Learning influence functions from incomplete observations. NeurIPS, Vol. 29 (2016)."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-020-00615-8"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/3099622.3099623"},{"key":"e_1_2_1_23_1","unstructured":"IZEA. 2021a. GUESS Eyewear. https:\/\/izea.com\/resources\/case-studies\/guess-eyewear."},{"key":"e_1_2_1_24_1","unstructured":"IZEA. 2021b. The Ultimate Guide to Influencer Marketing. https:\/\/izea.com\/resources\/influencer-marketing\/."},{"key":"e_1_2_1_25_1","unstructured":"IZEA. 2021c. Visit Tampa Bay. https:\/\/izea.com\/resources\/case-studies\/visit-tampa-bay."},{"key":"e_1_2_1_26_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_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00031-9"},{"key":"e_1_2_1_28_1","unstructured":"Andreas Krause and Carlos Guestrin. 2005. A note on the budgeted maximization of submodular functions. Citeseer."},{"key":"e_1_2_1_29_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_30_1","doi-asserted-by":"crossref","unstructured":"Yuchen Li Ju Fan George Ovchinnikov and Panagiotis Karras. 2019. Maximizing multifaceted network influence. In ICDE. 446--457.","DOI":"10.1109\/ICDE.2019.00047"},{"key":"e_1_2_1_31_1","unstructured":"LINQIA. 2019. How Much Budget Should You Spend on Influencer Marketing? https:\/\/www.linqia.com\/insights\/how-much-budget-should-you-spend-on-influencer-marketing\/."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2013.130610"},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","unstructured":"Hung T Nguyen Thang N Dinh and My T Thai. 2016. Cost-aware targeted viral marketing in billion-scale networks. In INFOCOM. 1--9.","DOI":"10.1109\/INFOCOM.2016.7524377"},{"key":"e_1_2_1_34_1","unstructured":"Srinivasan Parthasarathy. 2020. Adaptive Submodular Maximization under Stochastic Item Costs. In COLT. 3133--3151."},{"key":"e_1_2_1_35_1","volume-title":"Adaptive Influence Maximization with Myopic Feedback. arXiv preprint arXiv:1905.11663","author":"Peng Binghui","year":"2019","unstructured":"Binghui Peng and Wei Chen. 2019. Adaptive Influence Maximization with Myopic Feedback. arXiv preprint arXiv:1905.11663 (2019)."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-018-0252-3"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Lior Seeman and Yaron Singer. 2013. Adaptive seeding in social networks. In FOCS. 459--468.","DOI":"10.1109\/FOCS.2013.56"},{"key":"e_1_2_1_38_1","doi-asserted-by":"crossref","unstructured":"Chonggang Song Wynne Hsu and Mong Li Lee. 2016. Targeted influence maximization in social networks. In CIKM. 1683--1692.","DOI":"10.1145\/2983323.2983724"},{"key":"e_1_2_1_39_1","unstructured":"Shopify Staff. 2023. Influencer Marketing Prices: How Much Should You Pay. https:\/\/www.shopify.com\/blog\/influencer-pricing."},{"key":"e_1_2_1_40_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_41_1","doi-asserted-by":"crossref","unstructured":"Jing Tang Keke Huang Xiaokui Xiao Laks V. S. Lakshmanan Xueyan Tang Aixin Sun and Andrew Lim. 2019. Efficient Approximation Algorithms for Adaptive Seed Minimization. In SIGMOD. 1096--1113.","DOI":"10.1145\/3299869.3319881"},{"key":"e_1_2_1_42_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_43_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_44_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_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2016.2563397"},{"key":"e_1_2_1_46_1","volume-title":"Adaptive influence maximization in social networks: Why commit when you can adapt? arXiv preprint arXiv:1604.08171","author":"Vaswani Sharan","year":"2016","unstructured":"Sharan Vaswani and Laks VS Lakshmanan. 2016. Adaptive influence maximization in social networks: Why commit when you can adapt? arXiv preprint arXiv:1604.08171 (2016)."},{"key":"e_1_2_1_47_1","doi-asserted-by":"crossref","unstructured":"Ke Xu and Kai Han. 2018. Cost-Aware Targeted Viral Marketing with Time Constraints in Social Networks. In CollaborateCom. 75--91.","DOI":"10.1007\/978-3-030-12981-1_5"},{"key":"e_1_2_1_48_1","doi-asserted-by":"crossref","unstructured":"Yu Yang Xiangbo Mao Jian Pei and Xiaofei He. 2016. Continuous influence maximization: What discounts should we offer to social network users?. In SIGMOD. 727--741.","DOI":"10.1145\/2882903.2882961"},{"key":"e_1_2_1_49_1","doi-asserted-by":"crossref","unstructured":"Jing Yuan and Shao-Jie Tang. 2017. Adaptive discount allocation in social networks. In MobiHoc. 1--10.","DOI":"10.1145\/3084041.3084043"},{"key":"e_1_2_1_50_1","doi-asserted-by":"crossref","unstructured":"Ping Zhang Zhifeng Bao Yuchen Li Guoliang Li Yipeng Zhang and Zhiyong Peng. 2018. Trajectory-driven influential billboard placement. In SIGKDD. 2748--2757.","DOI":"10.1145\/3219819.3219946"},{"key":"e_1_2_1_51_1","doi-asserted-by":"crossref","unstructured":"Yipeng Zhang Yuchen Li Zhifeng Bao Baihua Zheng and HV Jagadish. 2021. Minimizing the regret of an influence provider. In SIGMOD. 2115--2127.","DOI":"10.1145\/3448016.3457257"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2019.2897608"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.14778\/3401960.3401961"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3617328","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3617328","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:46:15Z","timestamp":1750178775000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3617328"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,13]]},"references-count":53,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,11,13]]}},"alternative-id":["10.1145\/3617328"],"URL":"https:\/\/doi.org\/10.1145\/3617328","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,11,13]]}}}