Research On Optimization Methods For Profit Maximization In Social Networks

With the advancements in information science in the last two decades,social networks find importalt applications in viral marketing,where a few individuals are provided with free products,hoping that the product will be recursively reommended by each individual to his friends to create a large cascade of further adoptions.Although the existing works on influence maximization have obtained plentiful results in many ways,these works are based on the assumption that the number of influenced users determines the profit of product.However,the profit of some products relies on the interactions among the influenced users.Online games is an example,the game revenue depends on the participation and interaction of players.In this paper,we study the benefits related to strength of interactions among activated nodes.The main research contents and innovations are as follows.First,taking the marketing of online games as an example,we analyze the source of game product revenue and propose the Profit Maximization Problem(PMP)to find a seed set to maximize the profit between activated users in social networks.We analyze its modularity which is neither submodular nor supermodular and complexity which is NP-hard.We propose a new method named DS strategy for non-submodular optimization that decomposes the profit objective function into the differelce of two submodular functions which are mnotone nondecreasing.Based on the modular lower and upper bounds of decomposed submodular functions mentioned above,we propose four modular functions to approximate the original function and design four heuristic algorithms to solve the profit maximization problem.To address the complexity of computing the value of objective function,we design a new sampling method based on reverse set technology which is highly scalable instead of using Monte Carlo simulations.Through real data sets,we verify the effectiveness of our proposed algorithms.Second,due to inherent data limitation,the exact values of the edge probabilities could not be obtained through learniig method,what we can get is a probability range on each edge.We propose the Robust Profit Maximization Problem(RPMP)to find a seed that maximize the profit under the worst case propagation probability condition and the double sandwich algorithm is designed to solve the RPMP.It first solves the profit maximization problem on the minimum and maximum parameter vectors respectively,then we choose one solution that has higher total profit on the minimnum parameter vector as the output seed set.The profit maximization problem on the minimum and maximum paramter vector is non-submodular,to solve these two non-submodular problems,our sandwich algorithm finds submodular lower and upper bounds of it and solves them with greedy algorithm,then choose the solution with maximal total profit.We prove the double sandwich algorithm has a solution-dependent bound.In order to further improve the robustness of our algorithm,we study sampling methods to tighten parameter space of propagation probability.Then we extend the double sandwich algorithm with the uniform sampling method to solve RPMP and provide theoretical results on the uniform sample complexity for achieving a given robust ratio of the output seed set.The experimental results show that it significantly improve the robustness of the profit maximization problem.Last,to deal with the stochasticity caused by the dynamics of influence cascade,specifically,when a seed is selected,how the influence propagates is uncertain,we consider adaptive strategies to address the profit maximization problem.To this end,we propose Adaptive Profit Maximization Problem(APMP).We analyze its complexity and prove it is not adaptive submudular.Since our Adaptive Profit Maximization problem is not adaptive submodular,the greedy strategy cannot obtain a guaranteed approximate solution.To solve this problem,we find the upper bound and and lower bound of the objective function and prove both of them are adaptive submodular.Then we apply the sandwich strategy to our APMP and design an adaptive sandwich policy,which can obtain a data-dependent approximate solution.To the best of our knowledge,this is the first paper applying the sandwich strategy to the stochastic optimization problem which is not adaptive submodular and our proposed adaptive sandwich strategy can be used as a general optimization method for problems which are not adaptive submodular.