Budget-constrained profit maximization without non-negative objective assumption in social networks
Pages 1007 - 1030
Abstract
In this paper, we study the budget-constrained profit maximization problem with expensive seed endorsement, a derivation of the well-studied influence maximization and profit maximization in social networks. While existing research requires the non-negativity of the objective profit function, this paper considers real-world scenarios where costs may surpass revenue. Specifically, our problem can be regarded as maximizing the difference between a non-negative submodular function and a non-negative modular function under a knapsack constraint, allowing for negative differences. To tackle this challenge, we propose two algorithms. Firstly, we employ a twin greedy and enumeration technique to design a polynomial-time algorithm with a quarter weak approximation ratio, providing a balance between computational efficiency and solution quality. Then, we incorporate a threshold decreasing technique to enhance the time complexity of the first algorithm, yielding an improved computational efficiency while maintaining a reasonable level of solution accuracy. To our knowledge, this is the first paper to study the profit maximization beyond non-negativity and to propose polynomial-time algorithms with a constant bicriteria approximation ratio.
References
[1]
Brown JJ and Reingen PH Social ties and word-of-mouth referral behavior J. Consum. Res. 1987 14 3 350-362
[2]
Morris M Epidemiology and social networks: modeling structured diffusion Sociol. Methods Res. 1993 22 1 99-126
[3]
Borodin A, Filmus Y, and Oren J Saberi A Threshold models for competitive influence in social networks Internet and Network Economics 2010 Heidelberg Springer 539-550
[4]
Kempe, D., Kleinberg, J., Tardos, E.: Maximizing the spread of influence through a social network. In: Proc. ACM SIGKDD Int. Conf. Knowl. Discov. Data Min., pp. 137–146. Association for Computing Machinery (ACM), New York (2003)
[5]
Borgs, C., Brautbar, M., Chayes, J., Lucier, B.: Maximizing social influence in nearly optimal time. In: Proc. Annu. ACM SIAM Symp. Discrete Algorithms, pp. 946–957. Association for Computing Machinery, New York (2014)
[6]
Chen X, Hu X, and Wang C Approximation for the minimum cost doubly resolving set problem Theor. Comput. Sci. 2016 609 526-543
[7]
Hasan MA and Zaki MJ Aggarwal CC A survey of link prediction in social networks Social Network Data Analytics 2011 Boston Springer 243-275
[8]
Lappas, T., Terzi, E., Gunopulos, D., Mannila, H.: Finding effectors in social networks. In: Proc. ACM SIGKDD Int. Conf. Knowl. Discov. Data Min., pp. 1059–1068. Association for Computing Machinery (ACM), New York (2010)
[9]
Nemhauser GL, Wolsey LA, and Fisher ML An analysis of approximations for maximizing submodular set functions-i Math. Program. 1978 14 1 265-294
[10]
Ohsaka, N., Akiba, T., Yoshida, Y., Kawarabayashi, K.: Fast and accurate influence maximization on large networks with pruned monte-carlo simulations. In: Proc. Natl. Conf. Artif. Intell., 28, pp. 138–144. AAAI, California (2014)
[11]
Chen, W., Yuan, Y., Zhang, L.: Scalable influence maximization in social networks under the linear threshold model. In: Proc. IEEE Int. Conf. Data Min. ICDM, pp. 88–97. Institute of Electrical and Electronics Engineers Inc., New Jersey (2010)
[12]
Leskovec, J., Krause, A., Guestrin, C., Faloutsos, C., Vanbriesen, J., Glance, N.: Cost-effective outbreak detection in networks. In: Proc. ACM SIGKDD Int. Conf. Knowl. Discov. Data Min., pp. 420–429. Association for Computing Machinery, New York (2007)
[13]
Chen, W., Wang, Y., Yang, S.: Efficient influence maximization in social networks. In: Proc. ACM SIGKDD Int. Conf. Knowl. Discov. Data Min., pp. 199–208. Association for Computing Machinery, New York (2009)
[14]
Tang, Y., Xiao, X., Shi, Y.: Influence maximization: Near-optimal time complexity meets practical efficiency. In: Proc. ACM SIGMOD Int. Conf. Manage. Data, pp. 75–86. Association for Computing Machinery, New York (2014)
[15]
Tang, J., Tang, X., Yuan, J.: Influence maximization meets efficiency and effectiveness: a hop-based approach. In: Proc. IEEE/ACM Int. Conf. Adv. Soc. Netw. Anal. Min., ASONAM, pp. 64–71. Association for Computing Machinery, New York (2017)
[16]
Chen, W., Lin, T., Tan, Z., Zhao, M., Zhou, X.: Robust influence maximization. In: Proc. ACM SIGKDD Int. Conf. Knowl. Discov. Data Min., pp. 795–804. Association for Computing Machinery, New York (2016)
[17]
Zhang, H., Zhang, H., Kuhnle, A., Thai, M.T.: Profit maximization for multiple products in online social networks. In: Proc. IEEE INFOCOM, vol. 2016, pp. 1–9. Institute of Electrical and Electronics Engineers Inc., United States (2016)
[18]
Nguyen H and Zheng R On budgeted influence maximization in social networks IEEE J. Sel. Areas Commun. 2013 31 6 1084-1094
[19]
Lu, W., Lakshmanan, L.V.S.: Profit maximization over social networks. In: Proc. IEEE Int. Conf. Data Min. ICDM, pp. 479–488. Institute of Electrical and Electronics Engineers Inc., United States (2012)
[20]
Tang J, Tang X, and Yuan J Profit maximization for viral marketing in online social networks: algorithms and analysis IEEE Trans. Knowl. Data Eng. 2018 30 6 1095-1108
[21]
Bian, S., Guo, Q., Wang, S., Yu, J.X.: Efficient algorithms for budgeted influence maximization on massive social networks. In: Proc. VLDB Endow., Vol. 13, pp. 1498–1510. Springer, VLDB Endowment (2020)
[22]
Zhang Y, Yang X, Gao S, and Yang W Budgeted profit maximization under the multiple products independent cascade model IEEE Access 2019 7 20040-20049
[23]
Guo J, Chen T, and Wu W Budgeted coupon advertisement problem: algorithm and robust analysis IEEE Trans. Netw. Sci. Eng. 2020 7 3 1966-1976
[24]
Tang, J., Tang, X., Yuan, J.: Profit maximization for viral marketing in online social networks. In: Proc. Int. Conf. Netw. Protoc. ICNP, vol. 2016, pp. 1–10. IEEE Computer Society, California (2016)
[25]
Liu B, Li X, Wang H, Fang Q, Dong J, and Wu W Profit maximization problem with coupons in social networks Theor. Comput. Sci. 2020 803 22-35
[26]
Guo J and Wu W Continuous profit maximization: a study of unconstrained DR-submodular maximization IEEE Trans. Comput. Soc. Syst. 2021 8 3 768-779
[27]
Feige U, Mirrokni VS, and Vondrák J Maximizing non-monotone submodular functions SIAM J. Comput. 2011 40 4 1133-1153
[28]
Lu, C., Yang, W., Gao, S.: Regularized non-monotone submodular maximization. Optimization, 1–27 (2023)
[29]
Sviridenko M, Vondrak J, and Ward J Optimal approximation for submodular and supermodular optimization with bounded curvature Math. Oper. Res. 2017 42 4 1197-1218
[30]
Nikolakaki, S.M., Ene, A., Terzi, E.: An efficient framework for balancing submodularity and cost. In: Proc. ACM SIGKDD Int. Conf. Knowl. Discov. Data Min., pp. 1256–1266. Association for Computing Machinery, New York (2021)
[31]
Harshaw, C., Feldman, M., Ward, J., Karbasi, A.: Submodular maximization beyond non-negativity: Guarantees, fast algorithms, and applications. In: Int. Conf. Mach. Learn., ICML, vol. 2019, pp. 4684–4705. Association for Computing Machinery, New York (2019)
[32]
Feldman M Guess free maximization of submodular and linear sums Algorithmica 2021 83 3 853-878
[33]
Sviridenko M A note on maximizing a submodular set function subject to a knapsack constraint Oper. Res. Lett. 2004 31 1 41-43
[34]
Feldman M, Nutov Z, and Shoham E Practical budgeted submodular maximization Algorithmica 2023 85 5 1332-1371
[35]
Ene, A., Nguyen, H.L.: A nearly-linear time algorithm for submodular maximization with a knapsack constraint. In: 46th International Colloquium on Automata. Languages, and Programming (ICALP 2019), vol. 132, pp. 53–15312. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl, Germany (2019)
[36]
Gong S, Nong Q, Bao S, Fang Q, and Du DZ A fast and deterministic algorithm for knapsack-constrained monotone DR-submodular maximization over an integer lattice J. Global Optim. 2023 85 15-38
[37]
Buchbinder N and Feldman M Constrained submodular maximization via a nonsymmetric technique Math. Oper. Res. 2019 44 3 988-1005
[38]
Sun X, Zhang J, Zhang S, and Zhang Z Improved deterministic algorithms for non-monotone submodular maximization Theor. Comput. Sci. 2024 984
[39]
Jin T, Yang Y, Yang R, Shi J, Huang K, and Xiao X Unconstrained submodular maximization with modular costs: tight approximation and application to profit maximization IEEE Trans. Computat. Soc. Syst. 2021 14 10 1756-1768
[40]
Goldengorin B and Ghosh D A multilevel search algorithm for the maximization of submodular functions applied to the quadratic cost partition problem J. Global Optim. 2005 32 65-82
[41]
Gu S, Gao C, Huang J, and Wu W Profit maximization in social networks and non-monotone DR-submodular maximization Theor. Comput. Sci. 2023 957
[42]
Zhang G, Tatti N, and Gionis A Ranking with submodular functions on a budget Data Min. Knowl. Disc. 2022 36 3 1197-1218
Index Terms
- Budget-constrained profit maximization without non-negative objective assumption in social networks
Index terms have been assigned to the content through auto-classification.
Recommendations
Competitive profit maximization in social networks
We study the competitive profit maximization problem in a social network, which can be viewed as the profit maximization problem in a game-theoretic setting. We formulate two models called the profit maximization-agent (PM-A) game and the profit ...
A new genetic algorithm approach for optimizing bidding strategy viewpoint of profit maximization of a generation company
This paper presents a new approach for bidding strategy in a day-ahead market from the viewpoint of a generation company (GENCO) in order to maximize its own profit as a participant in the market. It is assumed that each GENCO submits its own bid as ...
Simple Mechanisms for Profit Maximization in Multi-item Auctions
EC '19: Proceedings of the 2019 ACM Conference on Economics and ComputationWe study a classical Bayesian mechanism design problem where a seller is selling multiple items to a buyer. We consider the case where the seller has costs to produce the items, and these costs are private information to the seller. How can the seller ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2024. Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
Publisher
Kluwer Academic Publishers
United States
Publication History
Published: 14 August 2024
Accepted: 07 May 2024
Received: 08 January 2024
Author Tags
Qualifiers
- Research-article
Funding Sources
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 14 Dec 2024