Study On Influence Maximization Algorithm Base On Betweenness-degree Index And Community Structure

There are all kinds of networks in the society,such as interpersonal network,social network,Internet,transportation network.With the progress and development of science and technology,the netw ork is also becoming increasingly complex.Especially in today,the the Internet is more developed.Relationship in the network is more and more obvious.The evolution of the network topology is becoming more and more severe.The study of these networks became the focus in academic circles.Especially in the transmission of information and advertising on the aspects,it becomes more and more popular.Therefore,it have a significant meaning to study the basic characteristics of these networks,the law of propag ation dynamics and the evolution process of network topology.The study on influence maximization algorithm aims to find an efficient and inexpensive strategy,The strategy select a set of sets that meet a given size as seed node sets.Under a certain propagation model,the coverage of influence propagation of seed sets can be maximized.The study of influence maximization is not only of great significan ce to the study of complex network theory,but also has a wide application prospect in product promotion,information dissemination,public opinion control and other aspects.In recent years,the study on influence maximization algorithm is quite extensive.Among the algorithm the most popular are algorithms based on greedy strategy and algorithms based on heuristic.The algorithms based on greedy strategy has a high accuracy rate,but its time complexity is very high.So these algorithms are not suitable for large network calculation.Heuristic algorithm has excellent operational efficiency,but its robustness and accuracy are not strong.Therefore,this paper takes the social network as the research object,analyzes and compares the advantages and feasibility of the centrality algorithm to solve the problem of influence maximization.In order to make up for the problem that the seed nodes selected based on the single centrality algorithm are heavily dependent on the network topology structure.The disadvantages of single centrality algorithm are optimized.Aiming at the local optimal problem of centrality algorithm,the network community structure is used to improve the global requirement of algorithm.The specific work of this paper is summarized as follows:First,the heuristic algorithm,using a single centricity index selection seed node,will rely h eavily on to the network topology.The seeds selected by algorithm based on a single centricity index is limited by a topological characteristics of network when seeds spread influence.It make the influence of coverage loss is bigger.In order to solve this problem,this paper comprehensive betweenness index and degree of index,and puts forward a new index makes choosing seeds in the influence maximization problem node.The evaluation of node's influence is more accurate.At the same time it increase the scope of influence in the network transmission.In order to solve the problem of overlapping influence among nodes,a discount strategy based on intermediate index is proposed to solve the problem of influence loss caused by overlapping influence.Secondly,whenalgorithm based on dielectric index evaluation in solve the problem of influence maxization,as a result of the betweenness-degree index of node is local characteristic of network,It will fall into local optima.In this paper,we use the community structure of complex networks to optimize the algorithm.The community structure of systemic makes the algorithm in the selection of seed node to give attention to global and avoids the problem of local optimum.Then,the betweenness-degree index evaluation algorithm based on the community structure still exist robustness problems.The time complexity of algorithm based on greedy strategy is too high.In this paper,we improves the robustness by using the greedy strategy and reducing the range of searching seed node,Finally,a large number of experiments are carried out to verify the proposed algorithm on 7 public complex network data sets.and the effectiveness and efficiency of the algorithm to solve the problem of influence maximization are proved by comparing with other classical influence maximization algorithms.