Accelerating Historical K-Core Search in Temporal Graphs
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_ | 1866915462149832704 |
|---|---|
| author | Ma, Zhuo Wen, Dong Chen, Kaiyu Fang, Yixiang Lin, Xuemin Zhang, Wenjie |
| author_facet | Ma, Zhuo Wen, Dong Chen, Kaiyu Fang, Yixiang Lin, Xuemin Zhang, Wenjie |
| contents | We study the temporal k-core component search (TCCS), which outputs the k-core containing the query vertex in the snapshot over an arbitrary query time window in a temporal graph. The problem has been shown to be critical for tasks such as contact tracing, fault diagnosis, and financial forensics. The state-of-the-art EF-Index designs a separated forest structure for a set of carefully selected windows, incurring quadratic preprocessing time and large redundant storage. Our method introduces the ECB-forest, a compact edge-centric binary forest that captures k-core of any arbitrary query vertex over time. In this way, a query can be processed by searching a connected component in the forest. We develop an efficient algorithm for index construction. Experiments on real-world temporal graphs show that our method significantly improves the index size and construction cost (up to 100x faster on average) while maintaining the high query efficiency. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_18151 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Accelerating Historical K-Core Search in Temporal Graphs Ma, Zhuo Wen, Dong Chen, Kaiyu Fang, Yixiang Lin, Xuemin Zhang, Wenjie Databases We study the temporal k-core component search (TCCS), which outputs the k-core containing the query vertex in the snapshot over an arbitrary query time window in a temporal graph. The problem has been shown to be critical for tasks such as contact tracing, fault diagnosis, and financial forensics. The state-of-the-art EF-Index designs a separated forest structure for a set of carefully selected windows, incurring quadratic preprocessing time and large redundant storage. Our method introduces the ECB-forest, a compact edge-centric binary forest that captures k-core of any arbitrary query vertex over time. In this way, a query can be processed by searching a connected component in the forest. We develop an efficient algorithm for index construction. Experiments on real-world temporal graphs show that our method significantly improves the index size and construction cost (up to 100x faster on average) while maintaining the high query efficiency. |
| title | Accelerating Historical K-Core Search in Temporal Graphs |
| topic | Databases |
| url | https://arxiv.org/abs/2508.18151 |