Fast Computing Betweenness Centrality with Virtual Nodes on Large Sparse Networks

Betweenness centrality is an essential index for analysis of complex networks. However, the calculation of betweenness centrality is quite time-consuming and the fastest known algorithm uses [Image: see text] time and [Image: see text] space for weighted networks, where [Image: see text] and [Image: see text] are the number of nodes and edges in the network, respectively. By inserting virtual nodes into the weighted edges and transforming the shortest path problem into a breadth-first search (BFS) problem, we propose an algorithm that can compute the betweenness centrality in [Image: see text] time for integer-weighted networks, where [Image: see text] is the average weight of edges and [Image: see text] is the average degree in the network. Considerable time can be saved with the proposed algorithm when [Image: see text], indicating that it is suitable for lightly weighted large sparse networks. A similar concept of virtual node transformation can be used to calculate other shortest path based indices such as closeness centrality, graph centrality, stress centrality, and so on. Numerical simulations on various randomly generated networks reveal that it is feasible to use the proposed algorithm in large network analysis.