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
Filename Description Size
p2033-wen.pdfAccepted version1.86 MB
Full metadata record
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: