{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T23:03:56Z","timestamp":1768518236241,"version":"3.49.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,6,13]],"date-time":"2023-06-13T00:00:00Z","timestamp":1686614400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["Grant Nos. 62276171 and 62002233"],"award-info":[{"award-number":["Grant Nos. 62276171 and 62002233"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,6,13]]},"abstract":"<jats:p>In this paper, we present an algorithmic study on how to surpass competitors in popularity by strategic promotions in social networks. We first propose a novel model, in which we integrate the Preferential Attachment (PA) model for popularity growth with the Independent Cascade (IC) model for influence propagation in social networks called PA-IC model. In PA-IC, a popular item and a novice item grab shares of popularity from the natural popularity growth via the PA model, while the novice item tries to gain extra popularity via influence cascade in a social network. The popularity ratio is defined as the ratio of the popularity measure between the novice item and the popular item. We formulate Popularity Ratio Maximization (PRM) as the problem of selecting seeds in multiple rounds to maximize the popularity ratio in the end. We analyze the popularity ratio and show that it is monotone but not submodular. To provide an effective solution, we devise a surrogate objective function and show that empirically it is very close to the original objective function while theoretically, it is monotone and submodular. We design two efficient algorithms, one for the overlapping influence and non-overlapping seeds (across rounds) setting and the other for the non-overlapping influence and overlapping seed setting, and further discuss how to deal with other models and problem variants. Our empirical evaluation further demonstrates that our proposed method consistently achieves the best popularity promotion compared to other methods. Our theoretical and empirical analyses shed light on the interplay between influence maximization and preferential attachment in social networks.<\/jats:p>","DOI":"10.1145\/3589309","type":"journal-article","created":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T20:26:45Z","timestamp":1687292805000},"page":"1-26","source":"Crossref","is-referenced-by-count":4,"title":["Popularity Ratio Maximization: Surpassing Competitors through Influence Propagation"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1223-6996","authenticated-orcid":false,"given":"Hao","family":"Liao","sequence":"first","affiliation":[{"name":"Shenzhen University, Shenzhen, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1097-9000","authenticated-orcid":false,"given":"Sheng","family":"Bi","sequence":"additional","affiliation":[{"name":"Shenzhen University, Shenzhen, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-8238-9367","authenticated-orcid":false,"given":"Jiao","family":"Wu","sequence":"additional","affiliation":[{"name":"Shenzhen University, Shenzhen, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0961-5365","authenticated-orcid":false,"given":"Wei","family":"Zhang","sequence":"additional","affiliation":[{"name":"Shenzhen University, Shenzhen, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5996-3395","authenticated-orcid":false,"given":"Mingyang","family":"Zhou","sequence":"additional","affiliation":[{"name":"Shenzhen University, Shenzhen, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3645-5520","authenticated-orcid":false,"given":"Rui","family":"Mao","sequence":"additional","affiliation":[{"name":"Shenzhen University, Shenzhen, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0065-3610","authenticated-orcid":false,"given":"Wei","family":"Chen","sequence":"additional","affiliation":[{"name":"Microsoft Research, Beijing, China"}]}],"member":"320","published-online":{"date-parts":[[2023,6,20]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.286.5439.509"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2012.122"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.70"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963499"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/080733991"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3-030-04648--4_24"},{"key":"e_1_2_2_7_1","volume-title":"Network Diffusion Models and Algorithms for Big Data (in Chinese)","author":"Chen Wei","unstructured":"Wei Chen. 2020. Network Diffusion Models and Algorithms for Big Data (in Chinese). Post and Telecom Press."},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.2200\/S00527ED1V01Y201308DTM037"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835934"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557047"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2010.118"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/502512.502525"},{"key":"e_1_2_2_13_1","unstructured":"D. Fudenberg and J. Tirole. 1993. Game Theory. MIT Press."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2011.132"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214046"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972825.40"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2012.79"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544831"},{"key":"e_1_2_2_20_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972771.60"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2433396.2433478"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2807843"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850578.2850581"},{"key":"e_1_2_2_25_1","doi-asserted-by":"crossref","unstructured":"G. L. Nemhauser L. A. Wolsey and M. L. Fisher. 1978. An analysis of the approximations for maximizing submodular set functions. Mathematical Programming.","DOI":"10.1007\/BF01588971"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915207"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775057"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/42.3-4.425"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220101"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557108"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183749"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2723734"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2593670"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-012-0262--1"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835935"},{"key":"e_1_2_2_36_1","series-title":"Series B, containing papers of a biological character","volume-title":"FR S. Philosophical transactions of the Royal Society of London","author":"Yule George Udny","year":"1925","unstructured":"George Udny Yule. 1925. II.?? mathematical theory of evolution, based on the conclusions of Dr. JC Willis, FR S. Philosophical transactions of the Royal Society of London. Series B, containing papers of a biological character, Vol. 213, 402--410 (1925), 21--87."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3589309","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3589309","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:46:13Z","timestamp":1750178773000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3589309"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,13]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6,13]]}},"alternative-id":["10.1145\/3589309"],"URL":"https:\/\/doi.org\/10.1145\/3589309","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,13]]}}}