A Unified and Scalable Algorithm Framework of User-Defined Temporal (k,X)-Core Query
- 3 January 2024
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 36 (7) , 2831-2845
Abstract
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,\mathcal {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 $\mathcal {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 $\mathcal {X}$ in a unified algorithm framework that guarantees scalability. For that, this journal paper proposes a taxonomy of measurement $\mathcal {X}(\cdot )$ and achieve our objective using a two-phase framework while $\mathcal {X}(\cdot )$ 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 $\mathcal {X}$ evaluation in each time zone with respect to the time insensitivity or monotonicity of $\mathcal {X}(\cdot )$ . By revealing two insightful concepts named tightest time interval and loosest time interval that bound time zones, the redundant core induction and unnecessary $\mathcal {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 $\mathcal {X}(\cdot )$ as a user-defined function.
Keywords
All Related Versions
Funding Information
- National Natural Science Foundation of China (61202036, 62272353, 62276193)
- Guangzhou Key Laboratory of Big Data and Intelligent Education (201905010009)
- Research Grants Council of Hong Kong (14203618, 14202919, 14205520)
This publication has 59 references indexed in Scilit:
- Generalized -core percolation on higher-order dependent networksApplied Mathematics and Computation, 2022
- Keyword aware influential community search in large attributed graphsInformation Systems, 2022
- Efficient continual cohesive subgraph search in large temporal graphsWorld Wide Web, 2021
- Efficient temporal core maintenance of massive graphsInformation Sciences, 2020
- -core: Theories and applicationsPhysics Reports, 2019
- A survey of community search over big graphsThe VLDB Journal, 2019
- Finding weighted k-truss communities in large networksInformation Sciences, 2017
- Effective and efficient attributed community searchThe VLDB Journal, 2017
- Geo-social group queries with minimum acquaintance constraintsThe VLDB Journal, 2017
- Towards an understanding of complex protein networksTrends in Cell Biology, 2001