.png){kind=icon}
.png){kind=icon}
Return
Efficiently querying connected components in large temporal graphs via scalable and maintainable indices
.png){kind=icon}
PRE
AI
DOI：10.1007/s00778-026-00977-5.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
In many real-world applications, the relationships between entities can be modeled as temporal graphs, where each edge is associated with a timestamp representing the interaction time. As a fundamental problem in network science, the connected component (CC) query has received tremendous research attention. Existing works on CC queries in the temporal graph find sets of vertices that are either connected in every timestamp of a time interval, or connected by paths with edges of increasing timestamps (i.e., time-respecting paths). However, these temporal constraints are too strict for applications without needing time-respecting paths. In this paper, we relax the above constraints by introducing a novel CC model, called window-CC, for both the undirected and directed temporal graphs in a given time window. We first propose online algorithms to query the window-CC, and further develop efficient and scalable index-based solutions. Besides, to handle queries on large dynamic temporal graphs, we also design efficient algorithms to dynamically update indices for new edges. Experimental results on real-world large-scale temporal graphs (both undirected and directed) demonstrate that our solutions achieve triple advantages:
Keywords:
Temporal graph/network
Connected component
Window-CC
Journal
T
IF:
0
Papers:
36
Citations:
0
Organization
View more organizations