Research On The Methods Of The Balanced Competitive Influence Maximization In Social Networks

With the fast development of technology,social network has become an important tool in people's daily lives.Through the Internet,the limitations of space fade away,and real-time access to information becomes possible.As a result,information dissemination and sharing are more quickly and easily on social platforms.Under such circumstance,one person's behavior and decision-making can be influenced by others,and social marketing began to attract more and more attention from both academia and industry.The problem of influence maximization,which finds influential individuals from social networks,so as to maximize the spread of product adoption or information propagation,has been extensively studied.However,previous studies mainly focused on the diffusion of single information or positive and negative information.When tackling information dissemination between similar competitors,there will be a balanced competition mechanism,and relevant research needs to be carried out in depth.Based on this observation,this thesis analyzes the propagation of influence diffusion of two similar competitive products in the same network at the same time.It studies how to find the most influential seed node set when the competitor's seed set is known.In this thesis,the formal definition of the problem is given.Through theoretical analysis,the proof of the problem characteristics is given,and an efficient and reliable approximate method is further designed.Finally,extensive experiments on real data sets are carried out to verify the efficiency and effectiveness of the proposed algorithm.Specifically,this thesis consists of the following contents:(1)This thesis introduces a new Balanced Competitive Influence Maximization(Ba CIM)problem,which considers the equilibrium characteristics of similar products' competitive propagation in the network.First,a Balanced Competitive Independent Cascade(BCIC)model is proposed,which describes how two similar competitive products propagate and compete in the same social network.Considering the communication strategy of competitors,Ba CIM's goal is to find a seed set with the size of k to maximize its own influence.In this thesis,it is proved that the Ba CIM problem under the BCIC model is NP-hard.The objective function of influence diffusion is monotone and submodular.On this basis,a greedy algorithm with approximate guarantee is proposed.(2)In order to solve the problem of high computational overhead and time complexity incurred by traditional greedy algorithm in dealing with large-scale networks,this thesis proposes a Blocked Reverse Influence Sampling(BRIS)algorithm based on the idea of reverse influence sampling.In this algorithm,the traditional reverse influence sampling routine is modified to support the new influence diffusion model.Experimental results on real social network datasets verified the effectiveness and efficiency of the algorithm.(3)In order to further improve the efficiency of BRIS algorithm,this thesis proposes an improved algorithm BRIS+.By utilizing the small world characteristics of real networks,an adequate sampling size can be quickly estimated in the construction of reverse reachable sets,and the sampling number ? ensures that the algorithm can return a(1-1 / e-)-approximate solution with high probability.In the seed selection stage,an incremental seed selection method based on Bottom-k Sketch is used to find the seed set covering the most reverse reachable sets.Extensive simulation results on real social network datasets verified the effectiveness and efficiency of the proposed algorithm.