Research On Approximate Betweenness Centrality For Large-scale Graph

The calculation of betweenness centrality is a basic problem in complex network analysis,it is used to measure the importance of a node in complex networks.In recent years,betweenness centrality has been widely used in social network analysis,combating the network of terrorist organizations,management of urban traffic network.The calculation of betweenness centrality is not only one of the hot topics in the field of computer science,but also attracts the attention of researchers in other fields.However,with the popularity of the mobile Internet,the explosive growth of the amount of data,the topology of the data is becoming more and more complex.The traditional algorithm of graph number calculation can not fully meet the requirement of the calculation of the graph,and even in some cases it is not practical because of the excessive calculation cost,so the hot spot of the research is gradually turned to an approximate betweenness calculation of the graph.In this paper,the research status of betweenness centrality at home and abroad is studied in depth,it is found that the algorithm can accurately calculate the betweenness value or the approximate algorithm for calculating the betweenness,computing on large scale graphs has their own merits and demerits.Accurate calculation of intermediate values requires the shortest path between any pair of nodes in a graph,it takes a lot of time to spend.At present,there are two main ideas for approximate computation of large-scale graph betweenness,the first is to select some source nodes for single source shortest path calculation based on source node sampling algorithm,the other is to increase the computation speed of the whole algorithm by approximating the shortest path.On this basis,the combination of the two,explore the strategy to select the source node and the number of source nodes selected,how to approximate the shortest path in large-scale graphs from the selected source nodes becomes a feasible research direction and solution.In this paper,we use the small world characteristics and scale-free properties of complex networks,Most of the shortest paths will pass through some nodes with highe degrees,This paper presents an algorithm for approximate computation of large scale graph betweenness,a node with high node degree is set as a central node,using VC theory in statistical learning to quantitatively calculate the number of central nodes.As a result,the number of selected data is no longer dependent on the size of the graph data,but depends only on the diameter of the graph nodes.Around the selected central nodes,the breadth first traversal algorithm is used to divide the whole graph into several regions,Mixed policies are selected on each region to select source nodes,that is,execute the Random policy,MaxMin policy,MaxSum policy in turn,until source node selection is completed in all partition areas.Finally,an experimental comparison with three other well-known betweenness approximation algorithms is given,it is proved that the large-scale approximation algorithm proposed in this paper has good efficiency and accuracy.