标题： 高效的时序简单路径图生成 显示英文标题

标题： Efficient Temporal Simple Path Graph Generation

摘要： 两个实体之间的交互通常发生在特定的时间戳，这可以建模为一个时序图。 基于时序路径探索顶点之间的关系是基本任务之一。 在本文中，我们进行了首次研究，提出并探讨了生成时序简单路径图（tspG）的问题，该图是由源顶点到目标顶点在给定时间区间内的所有时序简单路径组成的子图。 直接枚举所有时序简单路径并构建tspG计算成本很高。 为了加速处理，我们提出了一种名为在上界图中验证的方法。 它首先结合时序路径约束和简单路径约束，从原始图中排除无前景的边，从而在多项式时间内获得一个紧致的上界图，作为tspG的高质量近似。 然后，在上界图中进一步应用逃生边验证算法，以构建精确的tspG，而无需完全枚举给定顶点之间的所有时序简单路径。 最后，在10个现实世界的图上进行了全面实验，以证明所提出技术的效率和有效性。 显示英文摘要

摘要： 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 (tspG), 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 tspG is computationally expensive. To accelerate the processing, we propose an efficient method named Verification in Upper-bound 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 tspG in polynomial time. Then, an Escape Edges Verification algorithm is further applied in the upper-bound graph to construct the exact tspG without exhaustively enumerating all temporal simple paths between given vertices. Finally, comprehensive experiments on 10 real-world graphs are conducted to demonstrate the efficiency and effectiveness of the proposed techniques.