{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,28]],"date-time":"2024-08-28T11:08:51Z","timestamp":1724843331638},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"9","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2018,5]]},"abstract":"\n Given a social network\n G<\/jats:italic>\n , the influence maximization (IM) problem seeks a set\n S<\/jats:italic>\n of\n k<\/jats:italic>\n seed nodes in\n G<\/jats:italic>\n to maximize the expected number of nodes activated via an influence cascade starting from\n S.<\/jats:italic>\n Although a lot of algorithms have been proposed for IM, most of them only work under the\n non-adaptive<\/jats:italic>\n setting, i.e., when all\n k<\/jats:italic>\n seed nodes are selected before we observe how they influence other users. In this paper, we study the\n adaptive<\/jats:italic>\n IM problem, where we select the\n k<\/jats:italic>\n seed nodes in batches of equal size\n b<\/jats:italic>\n , such that the choice of the\n i<\/jats:italic>\n -th batch can be made after the influence results of the first\n i<\/jats:italic>\n - 1 batches are observed. We propose the first practical algorithms for adaptive IM with an approximation guarantee of 1 \u2212 exp(\u03be \u2212 1) for\n b<\/jats:italic>\n = 1 and 1 \u2212 exp(\u03be \u2212 1 + 1\/\n e<\/jats:italic>\n ) for\n b<\/jats:italic>\n > 1, where \u03be is any number in (0, 1). Our approach is based on a novel AdaptGreedy framework instantiated by non-adaptive IM algorithms, and its performance can be substantially improved if the non-adaptive IM algorithm has a small\n expected<\/jats:italic>\n approximation error. However, no current non-adaptive IM algorithms provide such a desired property. Therefore, we further propose a non-adaptive IM algorithm called EPIC, which not only has the same worst-case performance bounds with that of the state-of-the-art non-adaptive IM algorithms, but also has a reduced expected approximation error. We also provide a theoretical analysis to quantify the performance gain brought by instantiating AdaptGreedy using EPIC, compared with a naive approach using the existing IM algorithms. Finally, we use real social networks to evaluate the performance of our approach through extensive experiments, and the experimental experiments strongly corroborate the superiorities of our approach.\n <\/jats:p>","DOI":"10.14778\/3213880.3213883","type":"journal-article","created":{"date-parts":[[2018,6,12]],"date-time":"2018-06-12T18:15:11Z","timestamp":1528827311000},"page":"1029-1040","source":"Crossref","is-referenced-by-count":40,"title":["Efficient algorithms for adaptive influence maximization"],"prefix":"10.14778","volume":"11","author":[{"given":"Kai","family":"Han","sequence":"first","affiliation":[{"name":"University of Science and Technology of China"}]},{"given":"Keke","family":"Huang","sequence":"additional","affiliation":[{"name":"Nanyang Technological University"}]},{"given":"Xiaokui","family":"Xiao","sequence":"additional","affiliation":[{"name":"National University of Singapore"}]},{"given":"Jing","family":"Tang","sequence":"additional","affiliation":[{"name":"National University of Singapore"}]},{"given":"Aixin","family":"Sun","sequence":"additional","affiliation":[{"name":"Nanyang Technological University"}]},{"given":"Xueyan","family":"Tang","sequence":"additional","affiliation":[{"name":"Nanyang Technological University"}]}],"member":"320","published-online":{"date-parts":[[2018,5]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"https:\/\/bit.ly\/2I3A99p. https:\/\/bit.ly\/2I3A99p."},{"key":"e_1_2_1_2_1","unstructured":"http:\/\/snap.stanford.edu. http:\/\/snap.stanford.edu."},{"key":"e_1_2_1_3_1","unstructured":"https:\/\/sourceforge.net\/projects\/im-imm\/. https:\/\/sourceforge.net\/projects\/im-imm\/."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884466"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2012.122"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.spl.2013.01.023"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634144"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835934"},{"key":"e_1_2_1_9_1","first-page":"160","volume-title":"Proc. of ICML","author":"Chen Y.","year":"2013","unstructured":"Y. Chen and A. Krause . Near-optimal batch mode active learning and adaptive submodular optimization . In Proc. of ICML , pages 160 -- 168 , 2013 . Y. Chen and A. Krause. Near-optimal batch mode active learning and adaptive submodular optimization. In Proc. of ICML, pages 160--168, 2013."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/1568639"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/2208436.2208448"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00087"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3209582.3209595"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2740908.2744108"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/3099622.3099623"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915207"},{"key":"e_1_2_1_18_1","volume-title":"Feb 22","author":"Nguyen H. T.","year":"2017","unstructured":"H. T. Nguyen , M. T. Thai , and T. N. Dinh . Stop-and-stare: Optimal sampling algorithms for viral marketing in billion-scale networks. CoRR, abs\/1605.07990v3 , Feb 22 , 2017 . H. T. Nguyen, M. T. Thai, and T. N. Dinh. Stop-and-stare: Optimal sampling algorithms for viral marketing in billion-scale networks. CoRR, abs\/1605.07990v3, Feb 22, 2017."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.56"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183749"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3110025.3110041"},{"key":"e_1_2_1_22_1","volume-title":"An efficient and effective hop-based approach for inluence maximization in social networks. Social Network Analysis and Mining, 8(10)","author":"Tang J.","year":"2018","unstructured":"J. Tang , X. Tang , and J. Yuan . An efficient and effective hop-based approach for inluence maximization in social networks. Social Network Analysis and Mining, 8(10) , 2018 . J. Tang, X. Tang, and J. Yuan. An efficient and effective hop-based approach for inluence maximization in social networks. Social Network Analysis and Mining, 8(10), 2018."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2723734"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2593670"},{"key":"e_1_2_1_25_1","volume-title":"Adaptive influence maximization in social networks: Why commit when you can adapt? arXiv: 1604.08171","author":"Vaswani S.","year":"2016","unstructured":"S. Vaswani and L. V. S. Lakshmanan . Adaptive influence maximization in social networks: Why commit when you can adapt? arXiv: 1604.08171 , 2016 . S. Vaswani and L. V. S. Lakshmanan. Adaptive influence maximization in social networks: Why commit when you can adapt? arXiv: 1604.08171, 2016."},{"key":"e_1_2_1_26_1","first-page":"740","volume-title":"AAMAS","author":"Yadav A.","year":"2016","unstructured":"A. Yadav , H. Chan , A. Xin Jiang , H. Xu , E. Rice , and M. Tambe . Using social networks to aid homeless shelters: Dynamic influence maximization under uncertainty . In AAMAS , pages 740 -- 748 , 2016 . A. Yadav, H. Chan, A. Xin Jiang, H. Xu, E. Rice, and M. Tambe. Using social networks to aid homeless shelters: Dynamic influence maximization under uncertainty. In AAMAS, pages 740--748, 2016."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3213880.3213883","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:02:43Z","timestamp":1672221763000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3213880.3213883"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,5]]},"references-count":26,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2018,5]]}},"alternative-id":["10.14778\/3213880.3213883"],"URL":"http:\/\/dx.doi.org\/10.14778\/3213880.3213883","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2018,5]]}}}
