EUVIMEDEUVIMED entdecken
Crossref

Querying Cohesive Subgraphs in Temporal Graphs

Yinyu Liu, Kaiqiang Yu, Shengxin Liu, Cheng Long, Xun Zhou

Proceedings of the ACM on Management of Data · 18.05.2026 · 4 (3) · 1-27

DOI: 10.1145/3802103 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 18.05.2026. Verfasst von Yinyu Liu und 4 weiteren Autor:innen. Die Arbeit nennt 65 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Temporal graphs are widely used to model dynamic interactions across diverse domains, including social networks, biology, and e-commerce. Querying historical cohesive subgraphs, defined as extracting cohesive subgraphs from the graph snapshot induced by a given time interval, is a fundamental task in temporal graph analytics. Yet, current index-based methods are typically designed for a single model. This specialization yields high performance for a specific target but cannot be reused for others, which limits extensibility. In this paper, we propose a unified index-based framework to address this limitation. We focus on a generalized class of Historical CSMs (His-CSMs), which is characterized by two structural properties: non-overlapping (resultant subgraphs are vertex-disjoint) and monotonic (validity in a time interval implies validity in any super interval). This class includes prominent models such as historical connected components (His-CC) and historical k -cores (His-Core). To address the His-CSM query problem, we reduce queries for different CSMs to a single canonical query, the spanning connected component query, and design an index-based solution to answer this query efficiently. Building on this framework, we provide concrete instantiations for both His-CC and His-Core queries. Extensive experiments on real-world temporal graphs show that our method outperforms state-of-the-art baselines, achieving up to 60X speedups for His-CC and up to 100X speedups for His-Core.

Zitieren

APA

Liu, Y., Yu, K., Liu, S., Long, C., & Zhou, X. (2026). Querying Cohesive Subgraphs in Temporal Graphs. Proceedings of the ACM on Management of Data, 4(3), 1-27. https://doi.org/10.1145/3802103

Vancouver

Liu Y, Yu K, Liu S, Long C, Zhou X. Querying Cohesive Subgraphs in Temporal Graphs. Proceedings of the ACM on Management of Data. 2026;4(3):1-27. doi:10.1145/3802103

BibTeX
@article{Liu2026,
  author = {Liu, Yinyu and Yu, Kaiqiang and Liu, Shengxin and Long, Cheng and Zhou, Xun},
  title = {Querying Cohesive Subgraphs in Temporal Graphs},
  journal = {Proceedings of the ACM on Management of Data},
  year = {2026},
  volume = {4},
  number = {3},
  pages = {1--27},
  doi = {10.1145/3802103}
}
Kostenlos starten →