Abstract
We introduce the discount allocation problem to a new online social networks (OSNs) scenario where the nodes and the relationships between nodes are determined but the states of edges between nodes are unknown. We can know the states of all the edges centered on a node only when it becomes active. Different from most previous work on influence maximization discount allocation problem in OSNs, our goal is to minimize the discount cost that the marketer spends while ensuring at least Q customers who adopt the target product in the end in OSNs. We propose an online discount allocation policy to select seed users to spread the product information. The marketer initially selects one seed user to offer him a discount and observes whether he accepts the discount. If he accepts the discount, the marketer needs to observe how well this seed user contributes to the diffusion of product adoptions and how much discount he accepts. The remaining seeds are chosen based on the feedback of diffusion results obtained by all previous selected seeds. We propose two online discount allocation greedy algorithms under two different situations: uniform and non-uniform discounts allocation. We offer selected users discounts changing from the lowest to highest in the discount rate set until the users receive the discount and become seed users in non-uniform discount allocation situation, which saves the cost of firms comparing with the previous method that providing product to users for free. We present a theoretical analysis with bounded approximation ratios for the algorithms. Extensive experiments are conducted to evaluate the performance of the proposed online discount allocation algorithms on real-world online social networks datasets and the results demonstrate the effectiveness and efficiency of our methods.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Abebe R, Adamic LA, Kleinberg J (2018) Mitigating overexposure in viral marketing. In: Thirty-second AAAI conference on artificial intelligence
Choi J, Yi Y (2018) Necessary and sufficient budgets in information source finding with querying: adaptivity gap. In: IEEE international symposium on information theory (ISIT). IEEE, pp 2261–2265
Dhamal S (2018) Effectiveness of diffusing information through a social network in multiple phases. In: IEEE global communications conference (GLOBECOM). IEEE, pp 1–7
Domingos P, Richardson M (2001) Mining the network value of customers. In: Proceedings of the seventh ACM SIGKDD international conference on knowledge discovery and data mining. ACM, pp 57–66
Golovin D, Krause A (2011) Adaptive submodularity: theory and applications in active learning and stochastic optimization. J Artif Intell Res 42:427–486
Goyal A, Bonchi F, Lakshmanan LV (2011) A data-based approach to social influence maximization. Proc VLDB Endow 5(1):73–84
Han K, Huang K, Xiao X, Tang J, Sun A, Tang X (2018) Efficient algorithms for adaptive influence maximization. Proc VLDB Endow 11(9):1029–1040
Han K, Xu C, Gui F, Tang S, Huang H, Luo J (2018) Discount allocation for revenue maximization in online social networks. In: Proceedings of the eighteenth ACM international symposium on mobile ad hoc networking and computing. ACM, pp 121–130
Jurvetson S (2000) What exactly is viral marketing. Red Herring 78:110–112
Kempe D, Kleinberg J, Tardos É (2003) Maximizing the spread of influence through a social network. In: Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp 137–146
Newman ME (2001) The structure of scientific collaboration networks. Proc Natl Acad Sci 98(2):404–409
Opsahl T (2013) Triadic closure in two-mode networks: redefining the global and local clustering coefficients. Soc Netw 35(2):159–167
Richardson M, Domingos P (2002) Mining knowledge-sharing sites for viral marketing. In: Proceedings of the eighth ACM SIGKDD international conference on knowledge discovery and data mining. ACM, pp 61–70
Salha G, Tziortziotis N, and Vazirgiannis M (2018) Adaptive submodular influence maximization with myopic feedback. In: 2018 IEEE/ACM international conference on advances in social networks analysis and mining (ASONAM). IEEE, pp 455–462
Singer Y (2016) Influence maximization through adaptive seeding. ACM SIGecom Exch 15(1):32–59
Tang S (2018) Stochastic coupon probing in social networks. In: Proceedings of the 27th ACM international conference on information and knowledge management. ACM, pp 1023–1031
Tang S (2018) When social advertising meets viral marketing: sequencing social advertisements for influence maximization. In: Thirty-second AAAI conference on artificial intelligence,
Tang Y, Xiao X, and Shi Y (2014) Influence maximization: near-optimal time complexity meets practical efficiency. In: Proceedings of the 2014 ACM SIGMOD international conference on Management of data. ACM, pp 75–86
Tong G, Wu W, Tang S, Du D-Z (2017) Adaptive influence maximization in dynamic social networks. IEEE/ACM Trans Netw (TON) 25(1):112–125
Tong G, Wang R, Ling C, Dong Z, Li X (2020) Time-constrained adaptive influence maximization. arXiv preprint arXiv:2001.01742
Tong G, Wang R, Li X, Wu W, Du D-Z (2019) An approximation algorithm for active friending in online social networks. In: 2019 IEEE 39th international conference on distributed computing systems (ICDCS). IEEE, pp 1264–1274
Wang C, Chen W, Wang Y (2012) Scalable influence maximization for independent cascade model in large-scale social networks. Data Min Knowl Discov 25(3):545–576
Wang H, Liu B, Zhang X, Wu L, Wu W, Gao H (2016) List edge and list total coloring of planar graphs with maximum degree 8. J Comb Optim 32(1):188–197
Yang Y, Mao X, Pei J, He X (2016) Continuous influence maximization: what discounts should we offer to social network users? In: Proceedings of the 2016 international conference on management of data. ACM, pp 727–741
Yuan J, Tang S (2016) No time to observe: adaptive influence maximization with partial feedback. arXiv preprint arXiv:1609.00427
Yuan J, Tang S-J (2017) Adaptive discount allocation in social networks. In: Proceedings of the 18th ACM international symposium on mobile ad hoc networking and computing. ACM, p 22
Acknowledgements
This work is supported partially by the National Natural Science Foundation of China (Nos. 61772385, 61572370) and partially by NSF 1907472.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Ni, Q., Ghosh, S., Huang, C. et al. Discount allocation for cost minimization in online social networks. J Comb Optim 41, 213–233 (2021). https://doi.org/10.1007/s10878-020-00674-1
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-020-00674-1