On Querying Connected Components in Large Temporal Graphs

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. 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 index-based query algorithms. Experimental results on real large undirected and directed temporal graphs show that our best index-based query algorithms are up to three and two orders of magnitude faster than the two online algorithms, respectively. Moreover, compared to the baseline indices, our optimized indices cost much less space in both theory and practice. CCS Concepts: • Mathematics of computing → Paths and connectivity problems; Graph algorithms; • Theory of computation → Design and analysis of algorithms.