{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T16:44:48Z","timestamp":1780764288690,"version":"3.54.1"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2024,9,30]],"date-time":"2024-09-30T00:00:00Z","timestamp":1727654400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Hong Kong RGC GRF Grant","award":["No. 14217322"],"award-info":[{"award-number":["No. 14217322"]}]},{"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"]}]},{"name":"Tencent Rhino-Bird Focused Research Grant"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,10,1]]},"abstract":"<jats:p>\n                    Given a social network\n                    <jats:italic toggle=\"yes\">G<\/jats:italic>\n                    , a cost associated with each user, and an influence threshold \u03b7, the minimum cost seed selection problem (MCSS) aims to find a set of seeds that minimizes the total cost to reach \u03b7 users. Existing works are mainly devoted to providing an &lt;u&gt;e&lt;\/u&gt;xpected &lt;u&gt;c&lt;\/u&gt;overage &lt;u&gt;g&lt;\/u&gt;uarantee on reaching \u03b7, classified as MCSS-ECG, where their solutions either rely on an impractical influence oracle or cannot attain the expected influence threshold. More importantly, due to the expected coverage guarantee, the actual influence in a campaign may drift from the threshold evidently. Thus, the advertisers would like to request for a probability guarantee of reaching \u03b7. This motivates us to further solve the MCSS problem with a &lt;u&gt;p&lt;\/u&gt;robabilistic &lt;u&gt;c&lt;\/u&gt;overage &lt;u&gt;g&lt;\/u&gt;uarantee, termed MCSS-PCG.\n                  <\/jats:p>\n                  <jats:p>In this paper, we first propose our algorithm CLEAR to solve MCSS-ECG, which reaches the expected influence threshold without any influence oracle or influence shortfall but a practical approximation ratio. However, the ratio involves an unknown term (i.e., the optimal cost). Thus, we further devise the STAR method to derive a lower bound of the optimal cost and then obtain the first explicit approximation ratio for MCSS-ECG. In MCSS-PCG, it is necessary to estimate the probability that the current seeds reach \u03b7, to decide when to stop seed selection. To achieve this, we design a new technique named MRR, which provides efficient probability estimation with a theoretical guarantee. With MRR in hand, we propose our algorithm SCORE for MCSS-PCG, whose performance guarantee is derived by measuring the gap between MCSS-ECG and MCSS-PCG, and applying the theoretical results in MCSS-ECG. Finally, extensive experiments demonstrate that our algorithms achieve up to two orders of magnitude speed-up compared to alternatives while meeting the requirement of MCSS-PCG with the smallest cost.<\/jats:p>","DOI":"10.1145\/3677133","type":"journal-article","created":{"date-parts":[[2024,9,30]],"date-time":"2024-09-30T17:41:44Z","timestamp":1727718104000},"page":"1-26","source":"Crossref","is-referenced-by-count":4,"title":["Efficient Approximation Algorithms for Minimum Cost Seed Selection with Probabilistic Coverage Guarantee"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5495-8500","authenticated-orcid":false,"given":"Chen","family":"Feng","sequence":"first","affiliation":[{"name":"The Hong Kong Polytechnic University, Hong Kong, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-4647-9691","authenticated-orcid":false,"given":"Xingguang","family":"Chen","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9581-9817","authenticated-orcid":false,"given":"Qintian","family":"Guo","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong, Hong Kong"}],"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, Hong Kong"}],"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, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,9,30]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2024. Technical Report. https:\/\/github.com\/Planet-B612\/MCSS."},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Akhil Arora Sainyam Galhotra and Sayan Ranu. 2017. Debunking the myths of influence maximization: An in-depth benchmarking study. In SIGMOD. 651--666.","DOI":"10.1145\/3035918.3035924"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/3397230.3397244"},{"key":"e_1_2_1_4_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_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2010.118"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Edith Cohen Daniel Delling Thomas Pajor and Renato F Werneck. 2014. Sketch-based influence maximization and computation: Scaling up with guarantees. In CIKM. 629--638.","DOI":"10.1145\/2661829.2662077"},{"key":"e_1_2_1_7_1","unstructured":"Victoria Crawford Alan Kuhnle and My Thai. 2019. Submodular cost submodular cover with an approximate oracle. In ICML. 1426--1435."},{"key":"e_1_2_1_8_1","unstructured":"Artem Dogtiev. 2023. Influencer Marketing Costs. https:\/\/www.businessofapps.com\/marketplace\/influencer-marketing\/ research\/influencer-marketing-costs\/."},{"key":"e_1_2_1_9_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_10_1","doi-asserted-by":"crossref","unstructured":"Lidan Fan Zaixin Lu Weili Wu Bhavani Thuraisingham Huan Ma and Yuanjun Bi. 2013. Least cost rumor blocking in social networks. In ICDCS. 540--549.","DOI":"10.1109\/ICDCS.2013.34"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"e_1_2_1_12_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. 34, 6 (2020), 2844--2859.","journal-title":"IEEE Trans. Knowl. Data Eng."},{"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":"crossref","unstructured":"Guoju Gao Mingjun Xiao Jie Wu He Huang and Guoliang Chen. 2018. Minimum cost seed selection for multiple influences diffusion in communities. In MASS. 263--271.","DOI":"10.1109\/MASS.2018.00048"},{"key":"e_1_2_1_15_1","unstructured":"Malcolm Gladwell. 2006. The Tipping Point: How Little Things Can Make a Big Difference. Hachette UK."},{"key":"e_1_2_1_16_1","volume-title":"Case Study: DELL. https:\/\/goatagency.com\/case\/dell-3\/.","author":"GOAT.","year":"2020","unstructured":"GOAT. 2020. Case Study: DELL. https:\/\/goatagency.com\/case\/dell-3\/."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/2208436.2208448"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13278-012-0062-z"},{"key":"e_1_2_1_19_1","first-page":"1","article-title":"Efficient Algorithm for Budgeted Adaptive Influence Maximization: An Incremental RR-set Update Approach","volume":"1","author":"Guo Qintian","year":"2023","unstructured":"Qintian Guo, Chen Feng, Fangyuan Zhang, and Sibo Wang. 2023. Efficient Algorithm for Budgeted Adaptive Influence Maximization: An Incremental RR-set Update Approach. SIGMOD 1, 3 (2023), 1--26.","journal-title":"SIGMOD"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2019.2922271"},{"key":"e_1_2_1_21_1","first-page":"1029","article-title":"Efficient algorithms for adaptive influence maximization","volume":"11","author":"Han Kai","year":"2018","unstructured":"Kai Han, Keke Huang, Xiaokui Xiao, Jing Tang, Aixin Sun, and Xueyan Tang. 2018. Efficient algorithms for adaptive influence maximization. VLDB 11, 9 (2018), 1029--1040.","journal-title":"VLDB"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCYB.2020.2966593"},{"key":"e_1_2_1_23_1","first-page":"1","article-title":"Managing Conflicting Interests of Stakeholders in Influencer Marketing","volume":"1","author":"Huang Shixun","year":"2023","unstructured":"Shixun Huang, Junhao Gan, Zhifeng Bao, and Wenqing Lin. 2023. Managing Conflicting Interests of Stakeholders in Influencer Marketing. SIGMOD 1, 1 (2023), 1--27.","journal-title":"SIGMOD"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.knosys.2021.106797"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"David Kempe Jon Kleinberg and \u00c9va Tardos. 2003. Maximizing the spread of influence through a social network. In KDD. 137--146.","DOI":"10.1145\/956750.956769"},{"key":"e_1_2_1_26_1","unstructured":"Larry Kim. 2019. 9Ways To Improve Your Chances Of Getting Viral Marketing Campaigns. https:\/\/serpstat.com\/blog\/9-ways-to-improve-your-chances-of-getting-viral-marketing-campaigns\/."},{"key":"e_1_2_1_27_1","volume-title":"Md Abdul Alim, and My T Thai","author":"Kuhnle Alan","year":"2017","unstructured":"Alan Kuhnle, Tianyi Pan, Md Abdul Alim, and My T Thai. 2017. Scalable bicriteria algorithms for the threshold activation problem in online social networks. In INFOCOM. 1--9."},{"key":"e_1_2_1_28_1","volume-title":"Minimizing Seed Selection for Disseminating News with Probabilistic Coverage Guarantee. In International Conference on Electronic Commerce. 1--8.","author":"Lee Zhuo Qi","year":"2015","unstructured":"Zhuo Qi Lee and Wen-Jing Hsu. 2015. Minimizing Seed Selection for Disseminating News with Probabilistic Coverage Guarantee. In International Conference on Electronic Commerce. 1--8."},{"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":"publisher","DOI":"10.1109\/TNET.2019.2898413"},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Cheng Long and Raymond Chi-Wing Wong. 2011. Minimizing seed set for viral marketing. In ICDM. 427--436.","DOI":"10.1109\/ICDM.2011.99"},{"key":"e_1_2_1_32_1","volume-title":"Managing Complexity in Social Systems","author":"Mandl Christoph E","unstructured":"Christoph E Mandl. 2019. Managing Complexity in Social Systems. Springer."},{"key":"e_1_2_1_33_1","volume-title":"The tight constant in the Dvoretzky-Kiefer-Wolfowitz inequality. The Annals of Probability","author":"Massart Pascal","year":"1990","unstructured":"Pascal Massart. 1990. The tight constant in the Dvoretzky-Kiefer-Wolfowitz inequality. The Annals of Probability (1990), 1269--1283."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2013.130610"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915207"},{"key":"e_1_2_1_36_1","volume-title":"Groups Influence with Minimum Cost in Social Networks. In International Conference on Computational Data and Social Networks. 231--242","author":"Pham Phuong NH","year":"2021","unstructured":"Phuong NH Pham, Canh V Pham, Hieu V Duong, Trung Thanh Nguyen, and My T Thai. 2021. Groups Influence with Minimum Cost in Social Networks. In International Conference on Computational Data and Social Networks. 231--242."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comcom.2023.09.022"},{"key":"e_1_2_1_38_1","unstructured":"Whitney Rudeseal. 2023. 3 social media experts on how to go viral. https:\/\/www.stagwellmarketingcloud.com\/blog\/3-social-media-managers-on-how-to-go-viral."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.32657\/10220\/49508"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-019-00804-y"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigDataService49289.2020.00016"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(97)00182-8"},{"key":"e_1_2_1_43_1","volume-title":"Xueyan Tang, Aixin Sun, and Andrew Lim.","author":"Tang Jing","year":"2019","unstructured":"Jing Tang, Keke Huang, Xiaokui Xiao, Laks VS Lakshmanan, Xueyan Tang, Aixin Sun, and Andrew Lim. 2019. Efficient approximation algorithms for adaptive seed minimization. In SIGMOD. 1096--1113."},{"key":"e_1_2_1_44_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_45_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_46_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_47_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_48_1","first-page":"1","article-title":"Scapin: Scalable Graph Structure Perturbation by Augmented Influence Maximization","volume":"1","author":"Wang Yexin","year":"2023","unstructured":"Yexin Wang, Zhi Yang, Junqi Liu, Wentao Zhang, and Bin Cui. 2023. Scapin: Scalable Graph Structure Perturbation by Augmented Influence Maximization. SIGMOD 1, 2 (2023), 1--21.","journal-title":"SIGMOD"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11280-018-0607-9"},{"key":"e_1_2_1_50_1","doi-asserted-by":"crossref","unstructured":"Peng Zhang Wei Chen Xiaoming Sun Yajun Wang and Jialin Zhang. 2014. Minimizing seed set selection with probabilistic coverage guarantee in a social network. In KDD. 1306--1315.","DOI":"10.1145\/2623330.2623684"},{"key":"e_1_2_1_51_1","first-page":"1454","article-title":"Minimum vertex augmentation","volume":"14","author":"Zhao Jianwen","year":"2021","unstructured":"Jianwen Zhao and Yufei Tao. 2021. Minimum vertex augmentation. VLDB 14, 9 (2021), 1454--1466.","journal-title":"VLDB"},{"key":"e_1_2_1_52_1","doi-asserted-by":"crossref","unstructured":"Yuqing Zhu Deying Li and Zhao Zhang. 2016. Minimum cost seed set for competitive social influence. In INFOCOM. 1--9.","DOI":"10.1109\/INFOCOM.2016.7524472"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3677133","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3677133","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T17:12:04Z","timestamp":1774977124000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3677133"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,30]]},"references-count":52,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,10,1]]}},"alternative-id":["10.1145\/3677133"],"URL":"https:\/\/doi.org\/10.1145\/3677133","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,9,30]]}}}