Journal
IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING
Volume 7, Issue 3, Pages 1966-1976Publisher
IEEE COMPUTER SOC
DOI: 10.1109/TNSE.2020.2964882
Keywords
Robustness; Uncertainty; Greedy algorithms; Linear programming; Diffusion processes; Facebook; Profit maximization; coupon advertisement; social networks; influence diffusion; random greedy; continuous extension; discretization; robustness analysis
Funding
- National Science Foundation [1747818]
- Direct For Computer & Info Scie & Enginr
- Div Of Information & Intelligent Systems [1747818] Funding Source: National Science Foundation
Ask authors/readers for more resources
Coupon advertisement is everywhere in people's daily lives, and it is a common marketing strategy adopted by merchants. A problem, Budget Profit Maximization with Coupon Advertisement, is formulated in this article, which is a branch of classical profit maximization problem in social networks. Profit maximization has been researched intensively before, but its theoretical bound is not satisfactory usually because of NP-hardness, budget constraint and non-monotonicity. Learned from the lastest results, we proposed the B-Framework, which combines the ideas of Random Greedy and Continuous Double Greedy to obtain a more acceptable approximation ratio for this problem. For Continuous Double Greedy, it can be implemented by multilinear extension and discretized techniques. In addition, most of existing researches consider only maximizing total profit, however, in real scenarios, the diffusion probability is hard to determine due to the uncertainty. Then, we study the robustness for budgeted profit maximization, which can be used as a general strategy to analyze the robustness of non-monotone submodular function. It aims to obtain the best solution maximizing the ratio between the profit of any feasible seed set and the optimal seed set. We design LU-B-Framework first, and then we apply the method of uniform sampling to improve the robustness by reducing the uncertainty. The effectiveness and correctness of our algorithms are evaluated by heavy simulation on real-world social networks eventually.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available