{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T20:24:22Z","timestamp":1775679862693,"version":"3.50.1"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2020,9,28]],"date-time":"2020-09-28T00:00:00Z","timestamp":1601251200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100014718","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1747818, 1907472"],"award-info":[{"award-number":["1747818, 1907472"]}],"id":[{"id":"10.13039\/100014718","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":[[2020,12,31]]},"abstract":"<jats:p>Influence maximization problem attempts to find a small subset of nodes in a social network that makes the expected influence maximized, which has been researched intensively before. Most of the existing literature focus only on maximizing total influence, but it ignores whether the influential distribution is balanced through the network. Even though the total influence is maximized, but gathered in a certain area of social network. Sometimes, this is not advisable. In this article, we propose a novel seeding strategy based on community structure, and formulate the Influence Maximization with Community Budget (IMCB) problem. In this problem, the number of seed nodes in each community is under the cardinality constraint, which can be classified as the problem of monotone submodular maximization under the matroid constraint. To give a satisfactory solution for IMCB problem under the triggering model, we propose the IMCB-Framework, which is inspired by the idea of continuous greedy process and pipage rounding, and derive the best approximation ratio for this problem. In IMCB-Framework, we adopt sampling techniques to overcome the high complexity of continuous greedy. Then, we propose a simplified pipage rounding algorithm, which reduces the complexity of IMCB-Framework further. Finally, we conduct experiments on three real-world datasets to evaluate the correctness and effectiveness of our proposed algorithms, as well as the advantage of IMCB-Framework against classical greedy method.<\/jats:p>","DOI":"10.1145\/3399661","type":"journal-article","created":{"date-parts":[[2020,9,29]],"date-time":"2020-09-29T04:10:30Z","timestamp":1601352630000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":26,"title":["Influence Maximization"],"prefix":"10.1145","volume":"14","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, Richardson, Texas"}]},{"given":"Weili","family":"Wu","sequence":"additional","affiliation":[{"name":"The University of Texas at Dallas, Richardson, Texas"}]}],"member":"320","published-online":{"date-parts":[[2020,9,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.1145\/3035918.3035924"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.70"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.knosys.2017.07.029"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/080733991"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835934"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2010.118"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.70.066111"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/502512.502525"},{"key":"e_1_2_1_10_1","volume-title":"Wolsey","author":"Fisher Marshall L.","year":"1978"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 20th International Conference Companion on World Wide Web. ACM, 47--48","author":"Goyal Amit"},{"key":"e_1_2_1_12_1","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"Gr\u00f6tschel Martin"},{"key":"e_1_2_1_13_1","first-page":"2964882","article-title":"Budgeted coupon advertisement problem: Algorithm\u00a0and robust analysis","volume":"2020","author":"Guo Jianxiong","year":"2020","journal-title":"DOI:https:\/\/doi.org\/10.1109\/TNSE."},{"key":"e_1_2_1_14_1","first-page":"2944108","article-title":"Targeted protection maximization in social networks","volume":"2019","author":"Guo Jianxiong","year":"2019","journal-title":"DOI:https:\/\/doi.org\/10.1109\/TNSE."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCSS.2019.2926112"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502096"},{"key":"e_1_2_1_17_1","volume-title":"IRIE: A Scalable Influence Maximization Algorithm\u00a0for Independent Cascade Model and Its Extensions. Technical Report.","author":"Jung Kyomin","year":"2011"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"key":"e_1_2_1_19_1","volume-title":"Algorithms for online influencer marketing. ACM Transactions on Knowledge Discovery from Data 13, 1","author":"Lagr\u00e9e Paul","year":"2018"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281239"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 2016 International Conference on Management of Data. ACM, 695--710","author":"Nguyen Hung T."},{"key":"e_1_2_1_23_1","volume-title":"Rabiee","author":"Ramezani Maryam","year":"2018"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775057"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 29th AAAI Conference on Artificial Intelligence.","author":"Ryan"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2000.1989"},{"key":"e_1_2_1_27_1","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency.","author":"Schrijver Alexander","year":"2003"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2723734"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2593670"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374389"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835935"},{"key":"e_1_2_1_32_1","volume-title":"Rumor blocking through Online link deletion on social networks. ACM Transactions on Knowledge Discovery from Data 13, 2","author":"Yan Ruidong","year":"2019"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3399661","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3399661","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:33:32Z","timestamp":1750199612000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3399661"}},"subtitle":["Seeding Based on Community Structure"],"short-title":[],"issued":{"date-parts":[[2020,9,28]]},"references-count":32,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2020,12,31]]}},"alternative-id":["10.1145\/3399661"],"URL":"https:\/\/doi.org\/10.1145\/3399661","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,9,28]]},"assertion":[{"value":"2019-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-09-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}