The Research On Influence Maximization Algorithm Based On Benefit

With the rapid development of online social platforms,social media has become the main source for people to obtain information,and online marketing has become a mainstream marketing method.A large number of merchants publish their products on the Internet and conduct viral marketing through social networks.The key to marketing is to find influential seed users,maximize the scope of influence through word-of-mouth communication of seed users,and improve marketing effects.In order to find qualified torrent users,the influence maximization problem is proposed and widely studied in academia.Traditional influence maximization problems tend to focus only on reach,ignoring the commercial aspects of marketing.In the real viral marketing process,merchants only have a fixed marketing budget.Each time they select a seed user,they need to pay a price.Only by successfully influencing target users through seed users will they generate marketing benefits.Merchants mainly focus on how to use the fixed budget.Get maximum marketing benefits.The viral marketing problem in this business scenario is called the benefit maximization problem.The problem is to introduce three constraints of target node,budget and benefit cost on the basis of traditional problems,so that the computational complexity of the problem and the nature of the problem have changed,traditional algorithms can no longer be directly applied to maximize benefit influence,and It is difficult for other algorithms to run in this scenarios.In order to solve the above problems,the main innovations and contents of this paper are as follows:(1)Propose a benefit influence maximization algorithm(MCPR)based on marginal cost performance.The algorithm first defines the marginal cost performance,which is used to evaluate the importance of nodes in the problem of maximum benefit influence and then uses an iterative method to find an approximate self-consistent sequence that is very similar to the selection strategy of the greedy algorithm,while propagating the characteristics according to the independent cascade model.,design a cost-effective allocation method to speed up the iteration.Experiments show that the MCPR algorithm can effectively avoid the overlapping of benefit between nodes,achieve similar effects to the greedy algorithm,and greatly improve the running speed.(2)Propose a local DAG-based benefit influence maximization algorithm(TIDAG).Considering that the MCPR algorithm can only run on the independent cascade model and cannot run on the linear threshold model,this paper proposes the TIDAG algorithm by using the propagation characteristics of the linear threshold model.The algorithm abandons the use of Monte Carlo simulation to calculate returns,and instead calculates returns on a directed acyclic graph(DAG).By constructing a local DAG for each target node,the amount of computation is reduced on the premise of preserving the structural features to the greatest extent.Experiments on three real datasets show that TIDAG outperforms existing baseline algorithms.