Research On Influence Propagation Algorithm In Social Networks Based On Hypergraph

With the development of web technology,online social networks have sparked a wave of research,which not only enrich the way people communicate information,but also have an indispensable impact on the way people how to think and make decisions.Therefore,it is significant to select important influencers to make products or information the most widely distributed in the network,and this selection process is modeled as the influence maximization problem.The goal of this problem is to select the k most influential users in a given social network.This thesis considers new strategies and methods for the influence maximization problem.By introducing group influence and cost budget,we study the influence maximization problem with cost budget in hypergraphs.The main work of this thesis is as follows.Firstly,we study the influence maximization problem with cost budget in B-hypergraphs and formulate the information diffusion model of independent cascades in B-hypergraphs.Then we analyze the complexity of the problem and the submodularity of the objective function.For this problem,an improved budget greedy algorithm is proposed.The new algorithn overcomes the drawback of non-submodularity,which will destroy the approximation ratio.To further improve the performance,we optimize the budget greedy algorithm and propose a swapped budget greedy algorithm.We evaluate the algorithms on three B-hypergraph social networks.The results show that the improved budget greedy algorithm has an average 18.5%higher influence spreading than the existing algorithms,while the swapped budget greedy algorithm has an average 4.9%improvement over the improved budget greedy algorithm,which indicates that the swapped budget greedy algorithm performs better.Secondly,we study the influence maximization problem with cost budget in the undirected hypergraph,which is a further extension of the Bhypergraph.We propose a linear threshold model of information diffusion under undirected hypergraphs.The problem is NP-hard and the objective function is a non-submodular function.For this problem,the budgeted greedy algorithm with prior potential important nodes was proposed.Finally,we evaluate our algorithms with four publicly available social network datasets.In terms of influence spreading,our proposed algorithm has an average 47.3%higher than the weighted hypergraph algorithm and 11.1%higher than the budget greedy algorithm.In terms of running time,this algorithm is 15.3%faster than the budget greedy algorithm.The results show that the budgeted greedy algorithm with prior potential important nodes has obvious advantages in terms of running time and solution quality.