{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:51:38Z","timestamp":1773481898057,"version":"3.50.1"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2021,10]]},"abstract":"<jats:p>\n            Online Social Network (OSN) providers usually conduct advertising campaigns by inserting social ads into promoted posts. Whenever a user engages in a promoted ad, she may further propagate the promoted ad to her followers recursively and the propagation process is known as the\n            <jats:italic>word-of-mouth<\/jats:italic>\n            effect. In order to spread the promotion cascade widely and efficiently, the OSN provider often tends to select the influencers, who normally have large audiences over the social network, to initiate the advertising campaign. This marketing model, also termed as influencer marketing, has been gaining increasing traction and investment and is rapidly becoming one of the most widely-used channels in digital marketing.\n          <\/jats:p>\n          <jats:p>\n            In this paper, we formulate the problem for the OSN provider to derive the influence contributions of influencers given the campaign result, considering the viral propagation of the ads, namely\n            <jats:italic>influence contribution allocation (ICA)<\/jats:italic>\n            . We make a connection between ICA and the concept of Shapley value in cooperative game theory to reveal the rationale behind ICA. A naive method to obtain the solution to ICA is to enumerate all possible cascades delivering the campaign result, resulting in an exponential number of potential cascades, which is computationally intractable. Moreover, generating a cascade producing the exact campaign result is non-trivial. Facing the challenges, we develop an exact solution in linear time under the linear threshold (LT) model, and devise a\n            <jats:italic>fully polynomial-time randomized approximation scheme (FPRAS)<\/jats:italic>\n            under the independent cascade (IC) model. Specifically, under the IC model, we propose an efficient approach to estimate the expected influence contribution in probabilistic graphs modeling OSNs by designing a scalable sampling method with provable accuracy guarantees. We conduct extensive experiments and show that our algorithms yield solutions with remarkably higher quality over several baselines and improve the sampling efficiency significantly.\n          <\/jats:p>","DOI":"10.14778\/3489496.3489514","type":"journal-article","created":{"date-parts":[[2022,2,5]],"date-time":"2022-02-05T00:28:36Z","timestamp":1644020916000},"page":"348-360","source":"Crossref","is-referenced-by-count":6,"title":["Analysis of influence contribution in social advertising"],"prefix":"10.14778","volume":"15","author":[{"given":"Yuqing","family":"Zhu","sequence":"first","affiliation":[{"name":"Nanyang Technological University"}]},{"given":"Jing","family":"Tang","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology"}]},{"given":"Xueyan","family":"Tang","sequence":"additional","affiliation":[{"name":"Nanyang Technological University"}]},{"given":"Lei","family":"Chen","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology"}]}],"member":"320","published-online":{"date-parts":[[2022,2,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035924"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137635"},{"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\/3397230.3397244"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634144"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2008.04.004"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735703.2735706"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052608"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835934"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557047"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2010.118"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/502512.502525"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1186\/s40537-017-0101-8"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882929"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/574848"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2086737.2086741"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/2047485.2047492"},{"key":"e_1_2_1_18_1","volume-title":"Proc. ICLR.","author":"Goyal Anirudh","year":"2019","unstructured":"Anirudh Goyal , Philemon Brakel , William Fedus , Soumye Singhal , Timothy P. Lillicrap , Sergey Levine , Hugo Larochelle , and Yoshua Bengio . 2019 . Recall Traces: Backtracking Models for Efficient Reinforcement Learning . In Proc. ICLR. Anirudh Goyal, Philemon Brakel, William Fedus, Soumye Singhal, Timothy P. Lillicrap, Sergey Levine, Hugo Larochelle, and Yoshua Bengio. 2019. Recall Traces: Backtracking Models for Efficient Reinforcement Learning. In Proc. ICLR."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389740"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/3213880.3213883"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3209582.3209595"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-020-00615-8"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00062"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/3099622.3099623"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/2794367.2794376"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32241-9_48"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850578.2850581"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2013.130610"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915207"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380564"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064045"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775057"},{"key":"e_1_2_1_34_1","volume-title":"A Value for n-Person Games. Contributions to the Theory of Games 2, 28","author":"Shapley Lloyd S","year":"1953","unstructured":"Lloyd S Shapley . 1953. A Value for n-Person Games. Contributions to the Theory of Games 2, 28 ( 1953 ), 307--317. Lloyd S Shapley. 1953. A Value for n-Person Games. Contributions to the Theory of Games 2, 28 (1953), 307--317."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319881"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183749"},{"key":"e_1_2_1_37_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 Jing","year":"2018","unstructured":"Jing Tang , Xueyan Tang , and Junsong Yuan . 2018. An Efficient and Effective Hop-Based Approach for Inluence Maximization in Social Networks. Social Network Analysis and Mining 8, 10 ( 2018 ). Jing Tang, Xueyan Tang, and Junsong Yuan. 2018. 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_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2787757"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2018.8485975"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2723734"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2593670"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/3067421.3067429"},{"key":"e_1_2_1_43_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s11432-013-4895-5","article-title":"Influence maximization with limit cost in social network","volume":"56","author":"Wang Yue","year":"2013","unstructured":"Yue Wang , WeiJing Huang , Lang Zong , TengJiao Wang , and DongQing Yang . 2013 . Influence maximization with limit cost in social network . Science China Information Sciences 56 , 7 (2013), 1 -- 14 . Yue Wang, WeiJing Huang, Lang Zong, TengJiao Wang, and DongQing Yang. 2013. Influence maximization with limit cost in social network. Science China Information Sciences 56, 7 (2013), 1--14.","journal-title":"Science China Information Sciences"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882961"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3084041.3084043"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11390-016-1661-3"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.14778\/3401960.3401961"},{"key":"e_1_2_1_48_1","volume-title":"Efficient and Effective Influence Estimation","author":"Zhu Yuqing","year":"2021","unstructured":"Yuqing Zhu , Jing Tang , Xueyan Tang , Sibo Wang , and Andrew Lim . 2021. 2-hop+ Sampling : Efficient and Effective Influence Estimation . IEEE Transactions on Knowledge and Data Engineering ( 2021 ). Yuqing Zhu, Jing Tang, Xueyan Tang, Sibo Wang, and Andrew Lim. 2021. 2-hop+ Sampling: Efficient and Effective Influence Estimation. IEEE Transactions on Knowledge and Data Engineering (2021)."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3489496.3489514","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:16:05Z","timestamp":1672226165000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3489496.3489514"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10]]},"references-count":48,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,10]]}},"alternative-id":["10.14778\/3489496.3489514"],"URL":"https:\/\/doi.org\/10.14778\/3489496.3489514","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2021,10]]}}}