Abstract
Profit Maximization problem is an extension of Influence Maximization problem and aims to find a small set of initial adopters to maximize the expected profit generated by all the adopters after information dissemination. To the best of our knowledge, almost all the related works about Profit Maximization focus on one-entity diffusion model. In addition, emotion tendency and interest classification also play a role in real marketing process while their importance are underestimated in a lot of research. In this paper, we propose two novel nonsubmodular optimization problems, Generalized Self-profit Maximization in Attribute networks (GSMA) and Generalized Complementary-profit Maximization in Attribute networks (GCMA). Based on attribute networks’ community structure, these two problems consider the influence of both emotion tendency and interest classification on information dissemination process. GSMA problem focuses on supplement relationship and aims to maximize the expected value of profit. Whereas GCMA problem concentrates on the dependency relationship between entities and its goal is boosting the expected value of profit generated by adopter for an entity by selecting some initial adopters for its complementing entities. To solve these two problems, the R-GPMA algorithm framework which is inspired by sampling method and martingale analysis is designed. We evaluate our proposed algorithm by conducting experiments on randomly generated and real data sets and show that R-GPMA is superior in effectiveness and accuracy comparing with other baseline algorithms.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Data availibility
The NetHEPT dataset can be obtained from https://github.com/snowgy/Influence_Maximization/blob/master/test_data.
References
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, pp 795–804
Chen W, Wang C, Wang Y (2010) Scalable influence maximization for prevalent viral marketing in large-scale social networks. In: Proceedings of the ACM SIGKDD international conference on knowledge discovery and data mining. ACM, pp 1029–1038
Chung F, Lu L (2006) Concentration inequalities and martingale inequalities: a survey. Internet Math 3(1):79–127
Du L, Chen S, Gao S, Yang W (2021) Nonsubmodular constrained profit maximization from increment perspective. J Comb Optim 44:2598–2625
Fang Q, Chen X, Nong Q, Zhang Z, Cao Y, Feng Y, Sun T, Gong S, Du D (2020) General rumor blocking: an efficient random algorithm with martingale approach. Theor Comput Sci 803:82–93
Huang H, Shen H, Meng Z (2020) Community-based influence maximization in attributed networks. Appl Intell 50(2):354–364
Iyer RK, Bilmes JA (2013) Submodular optimization with submodular cover and submodular knapsack constraints. arXiv:1311.2106
Iyer RK, Bilmes JA (2014) Algorithms for approximate minimization of the difference between submodular functions, with applications. arXiv:1408.2051
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 137–146
Lu W, Chen W, Lakshmanan LV (2015) From competition to complementarity: comparative influence diffusion and maximization. Proc VLDB Endow 9(2):60–71
Moran F, Rani I (2014) Constrained monotone function maximization and the supermodular degree. arXiv:1407.6328
Narasimhan M, Bilmes JA (2012) A submodular-supermodular procedure with applications to discriminative structure learning. arXiv:1207.1404
Rishabh I, Stefanie J, Jeff B (2013) Curvature and optimal algorithms for learning and minimizing submodular functions. arXiv:1311.2110
Shang J, Zhou S, Li X, Liu L, Wu H (2017) CoFIM: a community-based framework for influence maximization on large-scale networks. Knowl Based Syst 117:88–100
Song J, Liu Y, Guo L, Xuan P (2019) Research on social network propagation model and influence maximization algorithm based on emotion. Comput Eng Appl 055(013):85–92
Tang J, Tang X, Yuan J (2018) Profit maximization for viral marketing in online social networks: algorithms and analysis. IEEE Trans Knowl Data Eng 30(6):1095–1108
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, association for computing machinery, New York, USA, pp 1539–1554
Tang J, Tang X, Yuan J (2017) Towards profit maximization for online social network providers. arXiv:1712.08963
Uriel F, Rani I (2013) Welfare maximization and the supermodular degree. In: Proceedings of the 4th conference on innovations in theoretical computer science—ITCS ’13. ACM Press, Berkeley, pp 247–256
Wang Z, Yang Y, Pei J, Chu L, Chen E (2017) Activity maximization by effective information diffusion in social networks. IEEE Trans Knowl Data Eng 29(11):2374–2387
Wu WL, Zhang Z, Du DZ (2019) Set function optimization. J Oper Res Soc China 7:183–193
Xinran H, David K (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
Acknowledgements
This is an extended version of a paper (Liman Du et al. 2021) presented in the 15th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2021). In this version, we further study the complementary relationship and propose another problem, named as Generalized Complementary-profit Maximization in Attribute networks (GCMA) problem. It focuses on the dependency relationship between entities which is different from the supplement relationship captured by Generalized Self-profit Maximization in Attribute networks (GSMA) problem which is proposed in the former version. In addition, we design some algorithms specially used to address GCMA problem and rewrite the whole algorithm framework to make it suitable for both GSMA problem and GCMA problem. Furthermore, we add the analysis of algorithm performance and supply more experiment results on both synthetic graph and real-world data sets.
Funding
This paper is supported by the National Natural Science Foundation of China under Grant Numbers 12071459 and 11991022 and the Fundamental Research Funds for the Central Universities under Grant Number E1E40107X2.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
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.
About this article
Cite this article
Du, L., Gao, S. & Yang, W. Generalized self-profit maximization and complementary-profit maximization in attribute networks. J Comb Optim 45, 2 (2023). https://doi.org/10.1007/s10878-022-00950-2
Accepted:
Published:
DOI: https://doi.org/10.1007/s10878-022-00950-2