Research On The Problem Of Maximizing Competitive Influence In Social Network

In the past few decades,the great development of the Internet has created large-scale communication platforms,such as We Chat and Twitter.Each platform can be modeled as a social network to represent the relationship and interaction between users.When a platform wants to be promoted,how should it choose a group of "influential" members in the network to "trigger" a series of influences so that as many people as possible use the platform.This is a classic problem of maximizing influence of one information in social networks.When multiple platforms implement the same promotion strategy on social networks at the same time,the analysis and research on the influence communication of individuals or single companies in social networks can no longer meet the needs of communication subjects,which leads to the problem of maximizing the competitive influence,that is,when competitors implement the same strategy,finding a seed set to maximize their own product information.Starting from reality,this paper studies competitive influence maximization problem based on two different social network influence models.The main work is as follows:We studied the weighted competitive influence maximization problem based on the competitive linear threshold model.We proved that this problem is NP-hard,and its corresponding objective function is a non-submodular and non-supermodular function,so the traditional greedy algorithm couldn’t provide a good approximate solution for this problem.Then,in order to solve the problem of maximizing the impact of weighted competition,we proposed a hybrid algorithm,ULS(UpperLower Squeeze)algorithm,by setting the upper and lower bound functions of the objective function for this problem,and we proved that this algorithm can effectively solve the competitive influence maximization problem based on the linear threshold model.We studied the weighted competitive influence maximization problem based on competitive independent cascade model.We proved that this problem is NP-hard,and its corresponding objective function is a non-submodular and non-supermodular function.Then,we proposed an R-ULS(R Upper-Lower Squeeze)algorithm to solve the problem of maximizing the influence of weighted competition.This algorithm sets the upper and lower bound functions for the objective function of this problem from the point of view of reverse reachable set,can get a better approximate solution with high probability in polynomial time.This paper conducts computational experiments on the ULS algorithm and the R-ULS algorithm on large networks corresponding to three different datasets.The experimental results show that the ULS algorithm has good effectiveness,and the R-ULS algorithm has good timeliness in addition to maintaining good effectiveness.