{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,8]],"date-time":"2026-09-08T03:38:19Z","timestamp":1788838699044,"version":"build-2803163510"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2021,5,10]],"date-time":"2021-05-10T00:00:00Z","timestamp":1620604800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1747818, 1907472"],"award-info":[{"award-number":["1747818, 1907472"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2021,10,31]]},"abstract":"<jats:p>Influence maximization problem attempts to find a small subset of nodes that makes the expected influence spread maximized, which has been researched intensively before. They all assumed that each user in the seed set we select is activated successfully and then spread the influence. However, in the real scenario, not all users in the seed set are willing to be an influencer. Based on that, we consider each user associated with a probability with which we can activate her as a seed, and we can attempt to activate her many times. In this article, we study the adaptive influence maximization with multiple activations (Adaptive-IMMA) problem, where we select a node in each iteration, observe whether she accepts to be a seed, if yes, wait to observe the influence diffusion process; if no, we can attempt to activate her again with a higher cost or select another node as a seed. We model the multiple activations mathematically and define it on the domain of integer lattice. We propose a new concept, adaptive dr-submodularity, and show our Adaptive-IMMA is the problem that maximizing an adaptive monotone and dr-submodular function under the expected knapsack constraint. Adaptive dr-submodular maximization problem is never covered by any existing studies. Thus, we summarize its properties and study its approximability comprehensively, which is a non-trivial generalization of existing analysis about adaptive submodularity. Besides, to overcome the difficulty to estimate the expected influence spread, we combine our adaptive greedy policy with sampling techniques without losing the approximation ratio but reducing the time complexity. Finally, we conduct experiments on several real datasets to evaluate the effectiveness and efficiency of our proposed policies.<\/jats:p>","DOI":"10.1145\/3447396","type":"journal-article","created":{"date-parts":[[2021,5,10]],"date-time":"2021-05-10T18:24:14Z","timestamp":1620671054000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":31,"title":["Adaptive Influence Maximization"],"prefix":"10.1145","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0994-3297","authenticated-orcid":false,"given":"Jianxiong","family":"Guo","sequence":"first","affiliation":[{"name":"The University of Texas at Dallas, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Weili","family":"Wu","sequence":"additional","affiliation":[{"name":"The University of Texas at Dallas, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,5,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.70"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972818.33"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939745"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835934"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCSS.2020.2998777"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2010.118"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/502512.502525"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/2208436.2208448"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-28684-6_12"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNSE.2020.2993042"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCSS.2019.2926112"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3399661"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCSS.2020.3001509"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/3213880.3213883"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 25th International Joint Conference on Artificial Intelligence. 3600--3608","author":"Hatano Daisuke","year":"2016","unstructured":"Daisuke Hatano , Takuro Fukunaga , and Ken-Ichi Kawarabayashi . 2016 . Adaptive budget allocation for maximizing influence of advertisements . In Proceedings of the 25th International Joint Conference on Artificial Intelligence. 3600--3608 . Daisuke Hatano, Takuro Fukunaga, and Ken-Ichi Kawarabayashi. 2016. Adaptive budget allocation for maximizing influence of advertisements. In Proceedings of the 25th International Joint Conference on Artificial Intelligence. 3600--3608."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-020-00615-8"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"key":"e_1_2_1_18_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. Retrieved from http:\/\/snap.stanford.edu\/data.  Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. Retrieved from http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 2016 International Conference on Management of Data. 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 Proceedings of the 2016 International Conference on Management of Data. 695--710 . 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 Proceedings of the 2016 International Conference on Management of Data. 695--710."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775057"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 29th AAAI Conference on Artificial Intelligence.","author":"Ryan","unstructured":"Ryan A. Rossi and Nesreen K. Ahmed. 2015. The network data repository with interactive graph analytics and visualization . In Proceedings of the 29th AAAI Conference on Artificial Intelligence. Retrieved from http:\/\/networkrepository.com Ryan A. Rossi and Nesreen K. Ahmed. 2015. The network data repository with interactive graph analytics and visualization. In Proceedings of the 29th AAAI Conference on Artificial Intelligence. Retrieved from http:\/\/networkrepository.com"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the Advances in Neural Information Processing Systems. 847--855","author":"Soma Tasuku","year":"2015","unstructured":"Tasuku Soma and Yuichi Yoshida . 2015 . A generalization of submodular cover via the diminishing return property on the integer lattice . In Proceedings of the Advances in Neural Information Processing Systems. 847--855 . Tasuku Soma and Yuichi Yoshida. 2015. A generalization of submodular cover via the diminishing return property on the integer lattice. In Proceedings of the Advances in Neural Information Processing Systems. 847--855."},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 31st AAAI Conference on Artificial Intelligence.","author":"Soma Tasuku","year":"2017","unstructured":"Tasuku Soma and Yuichi Yoshida . 2017 . Non-monotone dr-submodular function maximization . In Proceedings of the 31st AAAI Conference on Artificial Intelligence. Tasuku Soma and Yuichi Yoshida. 2017. Non-monotone dr-submodular function maximization. In Proceedings of the 31st AAAI Conference on Artificial Intelligence."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-018-1324-y"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220101"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319881"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183749"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2019.10.013"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2723734"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2593670"},{"key":"e_1_2_1_31_1","first-page":"3031057","article-title":"On adaptive influence maximization under general feedback models","volume":"2020","author":"Tong Guangmo","year":"2020","unstructured":"Guangmo Tong and Ruiqi Wang . 2020 . On adaptive influence maximization under general feedback models . IEEE Transactions on Emerging Topics in Computing (2020), 1--1. DOI: https:\/\/doi.org\/10.1109\/TETC. 2020 . 3031057 Guangmo Tong and Ruiqi Wang. 2020. On adaptive influence maximization under general feedback models. IEEE Transactions on Emerging Topics in Computing (2020), 1--1. DOI: https:\/\/doi.org\/10.1109\/TETC.2020.3031057","journal-title":"DOI: https:\/\/doi.org\/10.1109\/TETC."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2017\/546"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3447396","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3447396","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3447396","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:46:56Z","timestamp":1750178816000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3447396"}},"subtitle":["If Influential Node Unwilling to Be the Seed"],"short-title":[],"issued":{"date-parts":[[2021,5,10]]},"references-count":32,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,10,31]]}},"alternative-id":["10.1145\/3447396"],"URL":"https:\/\/doi.org\/10.1145\/3447396","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,5,10]]},"assertion":[{"value":"2020-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-05-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}