On querying historical k-cores
- Publisher:
- VLDB Endowment
- Publication Type:
- Conference Proceeding
- Citation:
- Proceedings of the VLDB Endowment, 2021, 14, (11), pp. 2033-2045
- Issue Date:
- 2021-01-01
Recently Added
Filename | Description | Size | |||
---|---|---|---|---|---|
p2033-wen.pdf | Accepted version | 1.86 MB |
Copyright Clearance Process
- Recently Added
- In Progress
- Open Access
This item is new to OPUS and is not currently available.
Many real-world relationships between entities can be modeled as temporal graphs, where each edge is associated with a timestamp or a time interval representing its occurrence. K-core is a fundamental model used to capture cohesive subgraphs in a simple graph and have drawn much research attention over the last decade. Despite widespread research, none of the existing works support the efficient querying of historical k-cores in temporal graphs. In this paper, given an integer k and a time window, we study the problem of computing all k-cores in the graph snapshot over the time window. We propose an index-based solution and several pruning strategies to reduce the index size. We also design a novel algorithm to construct this index, whose running time is linear to the final index size. Lastly, we conducted extensive experiments on several real-world temporal graphs to show the high effectiveness of our index-based solution.
Please use this identifier to cite or link to this item: