A Shortest Path Query Method over Temporal Graphs

Shortest path query has been extensively studied for decades of years. However, most of existing works focus on shortest path query over general graphs, a paucity of studies aim at temporal graphs, where there are multi-edges between two nodes and each edge is associated with a temporal interval, recording the start time and the end time of an event. Shortest path query over temporal graphs has a plethora of applications in urban traffic route planning, social network analysis, and communication network mining, to name but a few. Traditional shortest path algorithms on general graphs are not suitable for temporal graphs because subpaths of a shortest temporal path are not guaranteed to be the optimal substructures. Hence, in this paper, we propose a Compressed Transformed Graph tree (CTG-tree) based query method, which consists of a preprocessing stage and an online query stage. In the preprocessing stage, we transform the temporal graph into a general graph, propose a lossless compression method to reduce the scale of the transformed graph, use hierarchical partitioning technique to divide the compressed directed graph into subgraphs, and then build a CTG-tree index based on the partitioned subgraphs. The nodes of CTG-tree maintain shortest paths between some vertices in the corresponding subgraphs，save shortest paths between boundaries in the subgraphs of children nodes, and record shortest paths between boundaries of the subgraphs corresponding to the children nodes and those corresponding to the current node. In the online query stage, based on the constructed CTG-tree index, we develop an efficient shortest temporal path query method. Using four real-life temporal graphs, we experimentally demonstrate that our proposed method has the best query performance compared with the state-of-the-art methods.