Efficient Temporal Simple Path Graph Generation

Interactions between two entities often occur at specific timestamps, which can be modeled as a temporal graph. Exploring the relationships between vertices based on temporal paths is one of the fundamental tasks. In this paper, we conduct the first research to propose and investigate the problem of generating the temporal simple path graph (𝑡𝑠𝑝𝐺), which is the subgraph consisting of all temporal simple paths from the source vertex to the target vertex within the given time interval. Directly enumerating all temporal simple paths and constructing the 𝑡𝑠𝑝𝐺 is computationally expensive. To accelerate the processing, we propose an efficient method named Verification in Upperbound Graph. It first incorporates the temporal path constraint and simple path constraint to exclude unpromising edges from the original graph, which obtains a tight upper-bound graph as a high-quality approximation of the 𝑡𝑠𝑝𝐺 in polynomial time. Then, an Escape Edges Verification algorithm is further applied in the upper-bound graph to construct the exact 𝑡𝑠𝑝𝐺 without exhaustively enumerating all temporal simple paths between given vertices. Finally, comprehensive experiments on 10 realworld graphs are conducted to demonstrate the efficiency and effectiveness of the proposed techniques.

Contributions. We summarize the contributions in this paper.

• We conduct the first research to propose and investigate the problem of generating temporal simple path graph.

• To address this challenging problem, we propose an efficient method, namely VUG, consisting of two components, including Upper-bound Graph Generation for effectively yielding a high-quality approximate solution and Escaped Edges Verification for efficiently achieving the exact solution.

• We conduct extensive experiments on 10 real-word temporal graphs to compare VUG against baselines. The results demonstrate the effectiveness and efficiency of our methods.