关键词: 关键词: 介数中心度, 动态网络, 最短距离, 并行算法, 社区结构

Abstract: Betweenness centrality is a common metric for evaluating the importance of nodes in a graph. However, the update efficiency of betweenness centrality in large-scale dynamic graphs is not high enough to meet the application requirements. With the development of multi-core technology, algorithm parallelization has become one of the effective ways to solve this problem. Therefore, this paper proposes a parallel calculation method of betweenness centrality for dynamic networks (PCB). First, the time cost of redundant point pairs is reduced through community filtering, equidistant pruning and classification sifting; then, the deterministic of the algorithm is analyzed and processed to realize parallelization; finally, comparative experiments are conducted on real datasets and synthetic datasets, and the results show that the PCB algorithm is 4 times faster than the state-of-the-art methods. The proposed algorithm can effectively improve the update efficiency of betweenness centrality in dynamic networks, and has good scalability.

Key words: Keywords: betweenness centrality, dynamic network, shortest distance, parallel algorithm, community structure