2023/09/01 by Zhong Ming, Zhong, Ming, Junyong Yang +9
Computer Science · #Advanced Database Systems and Queries #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #Databases (cs.DB) #FOS: Computer and information sciences #Graph Theory and Algorithms
paper · pdf · doi:10.48550/arxiv.2309.00361
openalex publication_date 2023/09/01 · openalex created_date 2023/09/05 · openalex updated_date 2026/07/28
Querying cohesive subgraphs on temporal graphs (e.g., social network, finance network, etc.) with various conditions has attracted intensive research interests recently. In this paper, we study a novel Temporal (k,X)-Core Query (TXCQ) that extends a fundamental Temporal k-Core Query (TCQ) proposed in our conference paper by optimizing or constraining an arbitrary metric X of k-core, such as size, engagement, interaction frequency, time span, burstiness, periodicity, etc. Our objective is to address specific TXCQ instances with conditions on different X in a unified algorithm framework that guarantees scalability. For that, this journal paper proposes a taxonomy of measurement X(⋅) and achieve our objective using a two-phase framework while X(⋅) is time-insensitive or time-monotonic. Specifically, Phase 1 still leverages the query processing algorithm of TCQ to induce all distinct k-cores during a given time range, and meanwhile locates the ``time zones'' in which the cores emerge. Then, Phase 2 conducts fast local search and X evaluation in each time zone with respect to the time insensitivity or monotonicity of X(⋅). By revealing two insightful concepts named tightest time interval and loosest time interval that bound time zones, the redundant core induction and unnecessary X evaluation in a zone can be reduced dramatically. Our experimental results demonstrate that TXCQ can be addressed as efficiently as TCQ, which achieves the latest state-of-the-art performance, by using a general algorithm framework that leaves X(⋅) as a user-defined function.