Vertex Betweenness Centrality Computation Method over Temporal Graphs

In social network analysis, betweenness centrality is utilized to measure the contribution of a vertex to the network structure and is a widely used vertex importance metric. This metric evaluates the vertex importance mainly by counting the number of shortest paths through the vertices. The current studies for betweenness centrality computation mostly focus on general graphs, few focus on temporal ones. For general graphs, the betweenness centrality calculation methods are mainly designed based on the Brandes’ algorithm. The key theory is that the subpaths of a shortest path is still shortest, i.e., the optimal sub-structure property. However, temporal graphs contain temporal information, and there are various types of temporal paths that do not satisfy the optimal sub-structure property. Therefore, the theory and methods for betweenness centrality calculation on general graphs are no longer suitable for temporal graphs. In view of this, we define two types of temporal paths, i.e., strict (ascending timing order) and non-strict (non-descending timing order), and study the theory and methods for betweenness centrality on temporal graphs. An efficient two-stage iterative computing framework based on message propagation is proposed. The first stage adopts the top-down breadth-first traversal paradigm to calculate temporal shortest paths; the second stage employs the bottom-up method to calculate the contributions of the vertex’s successors and children to its betweenness centrality, and designs a message propagation based iterative accumulation method. In order to improve the efficiency and scalability, a multi-thread parallel FTBC (fast temporal betweenness centrality) algorithm based on OpenMP (open multiprocessing) framework is implemented. Using eight real temporal graphs, it’s showed that our proposed betweenness centrality calculation method has better computational performance than state-of-the-art methods in our experiment.