Efficient Temporal Simple Path Graph Generation
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915388380413952 |
|---|---|
| author | Tang, Zhiyang Wu, Yanping Zai, Xiangjun Chen, Chen Wang, Xiaoyang Zhang, Ying |
| author_facet | Tang, Zhiyang Wu, Yanping Zai, Xiangjun Chen, Chen Wang, Xiaoyang Zhang, Ying |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_10017 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Efficient Temporal Simple Path Graph Generation Tang, Zhiyang Wu, Yanping Zai, Xiangjun Chen, Chen Wang, Xiaoyang Zhang, Ying Databases 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. |
| title | Efficient Temporal Simple Path Graph Generation |
| topic | Databases |
| url | https://arxiv.org/abs/2507.10017 |