×

Diversified-profit maximization in competitive social advertising. (English) Zbl 1510.91127

Summary: Due to the important role that social networks play in advertisements and propaganda, influence maximization (IM) problem which aims at finding some influential users as seeds to trigger large online cascading influence spread has been a hot research topic in the past two decades. As an extension of classical IM problem, profit maximization (PM) problem is inspired by product promotion and focuses on the profit generated by consumer. Given that competitive social advertising is more common in real-world, a series of studies propose some versions of PM problem. However, the competition happening in the information dissemination of imperfect substitutes and the influence of potential consumers’ preference have been mostly ignored. Besides, to the best of our knowledge, no research pays attention on the fact that some companies may snatch seeds to limit the profits of their opponents. Therefore, we propose a novel competition-based diversified-profit maximization (CDM) problem and its adaptive version, i.e., adaptive competition-based diversified-profit maximization (ACDM) problem. Different from prior works, these problems take seed’s preference into consideration and use social welfare to reflect it. These two problems aim at selecting seeds and allocating them to marketers such that the sum of profit generated by consumers for a special entity after information dissemination and social welfare with respect to seed allocation reaches maximum. To address these two problems, we design an algorithm which combines the method of online allocation and the concept of Shapley value. Experimental results on three real-world data sets demonstrate the effectiveness of our proposed algorithm.

MSC:

91D30 Social networks; opinion dynamics
90B60 Marketing, advertising

Software:

CELF++; KONECT; CoFIM
Full Text: DOI

References:

[1] Ali K, Wang CY, Chen YS (2018) Boosting reinforcement learning in competitive influence maximization with transfer learning. In: 2018 IEEE/WIC/ACM international conference on web intelligence (WI), pp 395-400. doi:10.1109/WI.2018.00-62
[2] Ansari A, Dadgar M, Hamzeh A, Schlötterer J, Granitzer M (2019) Competitive influence maximization: integrating budget allocation and seed selection. arXiv:1912.12283
[3] Bharathi S, Kempe D, Salek H (2007) Competitive influence maximization in social networks. pp 306-311. doi:10.1007/978-3-540-77105-0_31
[4] Bozorgi, A.; Samet, S.; Kwisthout, J.; Wareham, T., Community-based influence maximization in social networks under a competitive linear threshold model, Knowl Based Syst, 134, 149-158 (2017) · doi:10.1016/j.knosys.2017.07.029
[5] Carnes T, Nagarajan C, Wild SM, van Zuylen A (2007) Maximizing influence in a competitive social network: a follower’s perspective. In: Proceedings of the ninth international conference on electronic commerce, ICEC’07. Association for Computing Machinery, New York, pp 351-360. doi:10.1145/1282100.1282167
[6] Chen W, Wang Y, Yang S (2009) Efficient influence maximization in social networks. In: Proceedings of the 15th ACM SIGKDD international conference on knowledge discovery and data mining, KDD’09. Association for Computing Machinery, New York, pp 199-208. doi:10.1145/1557019.1557047
[7] Chen W, Wang C, Wang Y (2010) Scalable influence maximization for prevalent viral marketing in large-scale social networks. pp 1029-1038. doi:10.1145/1835804.1835934
[8] Chen W, Lin T, Tan Z, Zhao M, Zhou X (2016) Robust influence maximization. In: Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining. ACM, San Francisco California USA, pp 795-804. doi:10.1145/2939672.2939745
[9] Du, L.; Chen, S.; Gao, S.; Yang, W., Nonsubmodular constrained profit maximization from increment perspective, J Comb Optim (2020) · Zbl 1504.90118 · doi:10.1007/s10878-021-00774-6
[10] Du, L.; Yang, W.; Gao, S.; Du, DZ; Du, D.; Wu, C.; Xu, D., Generalized self-profit maximization in attribute networks, Combinatorial optimization and applications, 333-347 (2021), Cham: Springer, Cham · Zbl 07550535 · doi:10.1007/978-3-030-92681-6_27
[11] Goyal A, Lu W, Lakshmanan LV (2011) Celf++: optimizing the greedy algorithm for influence maximization in social networks. In: Proceedings of the 20th international conference companion on world wide web, WWW’11. Association for Computing Machinery, New York, pp 47-48. doi:10.1145/1963192.1963217
[12] He X, Kempe D (2014) Stability of influence maximization. In: Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining—KDD’14. ACM Press, New York, pp 1256-1265. doi:10.1145/2623330.2623746
[13] Huang, H.; Shen, H.; Meng, Z., Community-based influence maximization in attributed networks, Appl Intell, 50, 2, 354-364 (2020) · doi:10.1007/s10489-019-01529-x
[14] Huzhang G, Huang X, Zhang S, Bei X (2017) Online roommate allocation problem. In: Proceedings of the twenty-sixth international joint conference on artificial intelligence, IJCAI-17, pp 235-241. doi:10.24963/ijcai.2017/34
[15] Kempe D, Kleinberg J, Tardos E (2003) Maximizing the spread of influence through a social network. In: Proceedings of the ACM SIGKDD international conference on knowledge discovery and data mining, pp 37-146. doi:10.1145/956750.956769 · Zbl 1337.91069
[16] Kunegis J (2013) KONECT—the Koblenz network collection. In: Proc. Int. Conf. on world wide web companion, pp 1343-1350. doi:10.1145/2487788.2488173
[17] Leskovec J, Krause A, Guestrin C, Faloutsos C, VanBriesen J, Glance N (2007) Cost-effective outbreak detection in networks. In: Proceedings of the 13th ACM SIGKDD international conference on knowledge discovery and data mining, KDD’07. Association for Computing Machinery, New York, pp 420-429. doi:10.1145/1281192.1281239
[18] Li H, Bhowmick SS, Cui J, Gao Y, Ma J (2015) Getreal: towards realistic selection of influence maximization strategies in competitive networks. In: Proceedings of the 2015 ACM SIGMOD international conference on management of data, SIGMOD’15. Association for Computing Machinery, New York, pp 1525-1537. doi:10.1145/2723372.2723710
[19] Li, H.; Pan, L.; Wu, P., Dominated competitive influence maximization with time-critical and time-delayed diffusion in social networks, J Comput Sci (2017) · doi:10.1016/j.jocs.2017.10.015
[20] Lin SC, Lin SD, Chen MS (2015) A learning-based framework to handle multi-round multi-party influence maximization on social networks. pp 695-704. doi:10.1145/2783258.2783392
[21] Lu, W.; Chen, W.; Lakshmanan, LVS, From competition to complementarity: comparative influence diffusion and maximization, Proc VLDB Endow, 9, 2, 60-71 (2015) · doi:10.14778/2850578.2850581
[22] Masucci A, Silva A (2014) Strategic resource allocation for competitive influence in social networks
[23] Masucci AM, Silva A (2017) Advertising competitions in social networks. doi:10.23919/ACC.2017.7963668
[24] Narayanam, R.; Narahari, Y., A shapley value-based approach to discover influential nodes in social networks, IEEE Trans Automat Sci Eng, 8, 1, 130-147 (2011) · doi:10.1109/TASE.2010.2052042
[25] Shang, J.; Zhou, S.; Li, X.; Liu, L.; Wu, H., CoFIM: a community-based framework for influence maximization on large-scale networks, Knowl Based Syst, 117, 88-100 (2017) · doi:10.1016/j.knosys.2016.09.029
[26] Shi Q, Wang C, Ye D, Chen J, Feng Y, Chen C (2019) Adaptive influence blocking: minimizing the negative spread by observation-based policies. In: 2019 IEEE 35th international conference on data engineering (ICDE), pp 1502-1513. doi:10.1109/ICDE.2019.00135
[27] Shi, Q.; Wang, C.; Ye, D.; Chen, J.; Zhou, S.; Feng, Y.; Chen, C.; Huang, Y., Profit maximization for competitive social advertising, Theor Comput Sci, 868, 12-29 (2021) · Zbl 1500.91104 · doi:10.1016/j.tcs.2021.03.036
[28] Song, J.; Liu, Y.; Guo, L.; Xuan, P., Research on social network propagation model and influence maximization algorithm based on emotion, J Comb Optim, 055, 13, 85-92 (2019)
[29] Sun L, Huang W, Yu PS, Chen W (2018) Multi-round influence maximization (extended version)
[30] Tang, S.; Yuan, J., Influence maximization with partial feedback, Oper Res Lett, 48, 1, 24-28 (2020) · Zbl 1525.91144 · doi:10.1016/j.orl.2019.10.013
[31] Tang Y, Shi Y, Xiao X (2015) Influence maximization in near-linear time: a martingale approach. In: Proceedings of the 2015 ACM SIGMOD international conference on management of data, SIGMOD’15. Association for Computing Machinery, New York, pp 1539-1554. doi:10.1145/2723372.2723734
[32] Tang J, Tang X, Yuan J (2017) Towards profit maximization for online social network providers. arXiv:1712.08963
[33] Tang, J.; Tang, X.; Yuan, J., Profit maximization for viral marketing in online social networks: algorithms and analysis, IEEE Trans Knowl Data Eng, 30, 6, 1095-1108 (2018) · doi:10.1109/TKDE.2017.2787757
[34] Varma, VS; Morărescu, IC; Lasaulce, S.; Martin, S., Marketing resource allocation in duopolies over social networks, IEEE Control Syst Lett, 2, 4, 593-598 (2018) · doi:10.1109/LCSYS.2018.2846185
[35] Varma, VS; Lasaulce, S.; Mounthanyvong, J.; Morărescu, IC, Allocating marketing resources over social networks: a long-term analysis, IEEE Control Syst Lett, 3, 4, 1002-1007 (2019) · doi:10.1109/LCSYS.2019.2919959
[36] Wang, X.; Xu, J.; Sun, Y.; Zhu, Z.; You, Z.; Tu, C., Near infrared passively Q-switched solid state laser based on Sb2Te3 topological insulator saturable absorber, J Lumin, 192, 1-5 (2017) · doi:10.1016/j.jlumin.2017.06.027
[37] Yan, R.; Zhu, Y.; Li, D.; Zilong, Y., Minimum cost seed set for threshold influence problem under competitive models, World Wide Web (2019) · doi:10.1007/s11280-018-0607-9
[38] Yu H, Kim SK, Kim J (2013) Scalable and parallelizable processing of influence maximization for large-scale social networks? In: Proceedings of the 2013 IEEE international conference on data engineering (ICDE 2013), ICDE’13. IEEE Computer Society, USA, pp 266-277. doi:10.1109/ICDE.2013.6544831
[39] Yuan J, Tang SJ (2017) Adaptive discount allocation in social networks. In: Proceedings of the 18th ACM international symposium on mobile ad hoc networking and computing, Mobihoc’17. Association for Computing Machinery, New York. doi:10.1145/3084041.3084043
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.