{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,10]],"date-time":"2025-05-10T23:01:10Z","timestamp":1746918070974},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2020,12]]},"abstract":"<jats:p>\n            Influence maximization (IM) has garnered a lot of attention in the literature owing to applications such as viral marketing and infection containment. It aims to select a small number of seed users to adopt an item such that adoption propagates to a large number of users in the network. Competitive IM focuses on the propagation of competing items in the network. Existing works on competitive IM have several limitations. (1) They fail to incorporate economic incentives in users' decision making in item adoptions. (2) Majority of the works aim to maximize the adoption of one particular item, and ignore the collective role that different items play. (3) They focus mostly on one aspect of competition - pure competition. To address these concerns we study competitive IM under a utility-driven propagation model called UIC, and study social welfare maximization. The problem in general is not only NP-hard but also NP-hard to approximate within any constant factor. We, therefore, devise instant dependent efficient approximation algorithms for the general case as well as a (1 - 1\/\n            <jats:italic>e - \u2208<\/jats:italic>\n            )-approximation algorithm for a restricted setting. Our algorithms outperform different baselines on competitive IM, both in terms of solution quality and running time on large real networks under both synthetic and real utility configurations.\n          <\/jats:p>","DOI":"10.14778\/3436905.3436920","type":"journal-article","created":{"date-parts":[[2021,2,22]],"date-time":"2021-02-22T17:23:50Z","timestamp":1614014630000},"page":"613-625","source":"Crossref","is-referenced-by-count":7,"title":["Maximizing social welfare in a competitive diffusion model"],"prefix":"10.14778","volume":"14","author":[{"given":"Prithu","family":"Banerjee","sequence":"first","affiliation":[{"name":"University of British Columbia, Vancouver, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wei","family":"Chen","sequence":"additional","affiliation":[{"name":"Microsoft Research, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Laks V. S.","family":"Lakshmanan","sequence":"additional","affiliation":[{"name":"University of British Columbia, Vancouver, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,2,22]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"[n. d.]. Twitter and Orkut Dataset. https:\/\/snap.stanford.edu\/data\/. Accessed: 2020-05-30.  [n. d.]. Twitter and Orkut Dataset. https:\/\/snap.stanford.edu\/data\/. Accessed: 2020-05-30."},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Ben Abramowitz and Elliot Anshelevich. 2018. Utilitarians Without Utilities: Maximizing Social Welfare for Graph Problems Using Only Ordinal Preferences. In AAAI. 894--901.  Ben Abramowitz and Elliot Anshelevich. 2018. Utilitarians Without Utilities: Maximizing Social Welfare for Graph Problems Using Only Ordinal Preferences. In AAAI. 894--901.","DOI":"10.1609\/aaai.v32i1.11453"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/2752939.2752950"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137635"},{"key":"e_1_2_1_5_1","unstructured":"Prithu Banerjee et al. [n. d.]. Maximizing Social Welfare in a Competitive Diffusion Model. https:\/\/arxiv.org\/abs\/2012.03354.  Prithu Banerjee et al. [n. d.]. Maximizing Social Welfare in a Competitive Diffusion Model. https:\/\/arxiv.org\/abs\/2012.03354."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319879"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3159652.3159702"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1781894.1781932"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-017-9759-8"},{"key":"e_1_2_1_10_1","volume-title":"Welfare economics","author":"Boadway Robin W"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634144"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963499"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.4324\/9781315624433"},{"key":"e_1_2_1_14_1","unstructured":"O. Celma. 2010. Last.fm Dataset - 1K users. http:\/\/www.dtic.upf.edu\/~ocelma\/MusicRecommendationDataset\/lastfm-1K.html.  O. Celma. 2010. Last.fm Dataset - 1K users. http:\/\/www.dtic.upf.edu\/~ocelma\/MusicRecommendationDataset\/lastfm-1K.html."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2796314.2745853"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735703.2735706"},{"key":"e_1_2_1_17_1","volume-title":"An Issue in the Martingale Analysis of the Influence Maximization Algorithm IMM. arXiv preprint arXiv:1808.09363","author":"Chen Wei","year":"2018"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835934"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2010.118"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/2601921"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2010.52"},{"key":"e_1_2_1_22_1","volume-title":"The Submodular Welfare Problem with Demand Queries. TOC","author":"Feige Uriel","year":"2010"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/3294996.3295219"},{"key":"e_1_2_1_24_1","unstructured":"Xinran He et al. 2012. Influence blocking maximization in social networks under the competitive linear threshold model. In ICDM.  Xinran He et al. 2012. Influence blocking maximization in social networks under the competitive linear threshold model. In ICDM."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/3099622.3099623"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2012.79"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627905"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746626"},{"key":"e_1_2_1_30_1","unstructured":"Paul Lamere. 2008. LastFM-ArtistTags2007 dataset. http:\/\/musicmachinery.com\/2010\/11\/10\/lastfm-artisttags2007\/.  Paul Lamere. 2008. LastFM-ArtistTags2007 dataset. http:\/\/musicmachinery.com\/2010\/11\/10\/lastfm-artisttags2007\/."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-014-0366-x"},{"key":"e_1_2_1_32_1","volume-title":"Social Graphs: A Survey. TKDE","author":"Yuchen Li","year":"2018"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00047"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2015.06.012"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487649"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850578.2850581"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487649"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.6.1.58"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915207"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/1296179"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2010.153"},{"key":"e_1_2_1_42_1","unstructured":"Tao Sun et al. 2011. Participation Maximization Based on Social Influence in Online Discussion Forums. In ICWSM.  Tao Sun et al. 2011. Participation Maximization Based on Social Influence in Online Discussion Forums. In ICWSM."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183749"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2723734"},{"key":"e_1_2_1_45_1","doi-asserted-by":"crossref","unstructured":"Yuqing Zhu et al. 2016. Minimum cost seed set for competitive social influence. In INFOCOM.  Yuqing Zhu et al. 2016. Minimum cost seed set for competitive social influence. In INFOCOM.","DOI":"10.1109\/INFOCOM.2016.7524472"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3436905.3436920","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:30:00Z","timestamp":1672223400000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3436905.3436920"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12]]},"references-count":45,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["10.14778\/3436905.3436920"],"URL":"https:\/\/doi.org\/10.14778\/3436905.3436920","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2020,12]]}}}