Durable Community Search on Temporal Graphs

This paper studies the problem of durable community search on temporal graphs. Given a temporal graph G_[s,e], a positive integer k, and a keyword set Q, we attempt to detect all connected k-trusses H of G_[s,e] with (1) the keywords of H cover Q, (2) H has the largest existence interval. (3) there is no such k-truss H^′⊇H while also satisfying (1) and (2). This problem has many applications, such as bio-network analysis and anomaly detection. However, there is no efficient solution in the literature. In this paper, we first analyze the existence of durable communities among related time intervals and then devise a binary search-based method, namely BinaryDCS, which can skip fruitless intervals correctly. Besides, we optimize the intersection of snapshots by the segment tree. After that, we develop a novel framework, i.e., IncrementDCS, to enhance the pruning capacity by exploring the subintervals more orderly. Comprehensive performance studies on 3 real datasets show that our proposals outperform the baselines by up to 2 orders of magnitude.