Research On Computation Method Of Betweenness Centrality For Road Networks

Centrality metrics play an important role in detecting central and influential nodes in various types of networks such as social networks,biological networks and power networks.Among the centrality metrics,there has been an increasing interest in betweenness centrality,which measures the extent to which nodes maintain the flow of information between any other pairs of nodes in the network.Betweenness centrality is widely used to identify opinion leaders or influencers in social networks,vulnerabilities in computer networks,critical intersections in road transport networks.With the increasing size of networks,how to improve the efficiency of computing betweenness centrality has become one of the hot research topics.This paper focuses on improving the efficiency of computing betweenness centrality on road networks,which have many applications,including traffic planning,road maintenance and traffic flow prediction.The main research of this paper is as follows:Firstly,this paper introduces the state-of-the-art Brandes algorithm,summarising the three elements of the first phase of the algorithm.A new framework for computing the three elements based on index is proposed: predecessor set is computed by querying the shortest distance between any two vertices at the(shortest path distance)index,and then the topological ordering is used to obtain information on the order of vertices and the number of paths.Secondly,this paper combines the search-based Brandes’ algorithm with the index-based framework proposed in this paper to propose a hybrid-based algorithm for the computation of betweenness centrality,and gives corresponding solutions for the vertex ordering,threshold and pruning that affect the efficiency of the algorithm.Finally,in the experimental part,real road network data sets are used for testing.The experimental results show that the hybrid-based solution proposed in this paper can compute the betweenness centrality more efficiently than the state-of-the-art algorithm,providing a new idea and method for computing the betweenness centrality.