Research On Influence Maximization Based On Semi-local Centrality And Structural Holes

With the rapid popularization of social networks,complex network issues are getting closer to our public lives.The most representative of this field is the issue of influence maximization.The study of influence maximization is the foundation of wordof-mouth marketing and viral marketing.It is involved in many fields such as social networks,infectious disease control,and transportation networks.It has important research significance and practical application value.The purpose of this question is to find a set of seed nodes that can maximize the spread of influence.Influence maximization algorithms are mainly divided into two types,one is a greedy algorithm with high accuracy and low efficiency,and the other is a heuristic algorithm with high efficiency but insufficient accuracy.The algorithm in this paper aims to reduce the time cost of the greedy algorithm and improve the accuracy of the heuristic algorithm.Heuristic algorithms generally rely on influence metrics.This article starts with the influence measurement,first based on the semi-local centrality measurement,and puts forward the LSH measurement based on its shortcomings and combined with the idea of structural holes.This metric can not only accurately select nodes at the core position in the network,but also identify nodes at the edge of the network and occupy structural holes.Therefore,this metric can more comprehensively evaluate the influence of nodes in the network.We have proved that the measurement is an accurate and efficient measurement method through experiments on real data sets.Subsequently,we introduced the LSH metric of this paper into the influence maximization problem,and proposed an influence discount strategy for nodes in the secondorder neighborhood of the LSH metric.The discount strategy mainly involves the propagation probability and the clustering coefficient and the number of activated neighbor nodes.According to this discount strategy,a heuristic LSD algorithm for the problem of influence maximization is proposed.Experiments with 10 real data sets prove that the accuracy of the result set of the LSD algorithm is close to the greedy algorithm and is better than most heuristic algorithms.At the end of this paper,heuristic algorithm ideas and greedy algorithm are combined,and an algorithm based on iterative calculation and greedy strategy is proposed,it is LSRank?CELF algorithm.In the calculation process,we use the LSD algorithm of this paper to provide the key initial sorting sequence for the iterative stage.In the algorithm process,iterative calculation is used to reduce the computational time cost of the greedy phase,and the result of the greedy phase will be used to improve the accuracy of the iterative phase to provide a more accurate node candidate set.We conducted experiments on 9 real data sets and proved that the accuracy of the algorithm is equivalent to the CELF algorithm,and the computational efficiency is greatly improved.