关键词: 时序图, 树分解, 索引, 最短路径, 最短路径计数

Abstract: The shortest path count is an important research problem in graph computing, which aims to query the number of shortest paths between vertices, which is widely used in real-world data analysis. At present, more and more networks can be modeled as temporal graphs, but there is no research work on the shortest path count query problem of temporal graphs. Due to the addition of time information to temporal graphs, the shortest path counting method in static graphs is no longer suitable for temporal graphs, and querying on large-scale temporal graphs is more challenging. In order to solve the shortest path count problem of temporal graphs, a shortest path count query algorithm based on temporal tree decomposition is proposed. The algorithm includes three stages, firstly, the temporal tree decomposition algorithm is designed according to the attributes of the temporal graphs, and the temporal graphs is transformed into a tree structure; Then, according to the convex path definition, the TG-TL (Temporal Graphs-Tree Label) index is constructed on the temporal tree decomposition. Finally, the structural information of index and tree decomposition is used to query the shortest number of paths. Experiments on four real datasets verify the efficiency and effectiveness of the proposed algorithm on the shortest path counting problem of temporal graphs.

Key words: temporal graphs, tree decomposition, index, shortest path, shortest path counting