跳到主要导航 跳到搜索 跳到主要内容

Querying Historical k-Dense Subgraphs on Temporal Graphs

  • University of Science and Technology Beijing
  • Beijing Institute of Technology

科研成果: 书/报告/会议事项章节 › 会议稿件 › 同行评审

摘要

Historical cohesive subgraph queries in temporal graphs identify dense substructures within snapshots corresponding to given time intervals, gaining attention due to their broad applications. Existing works primarily focus on k-core, which fails to consider subgraph density (measured as the ratio of edges to vertices) and may fragment natural community structures. Borradaile et al. introduced density decomposition, hierarchically organizing graphs into nested k-dense subgraphs, with each subgraph ensuring a minimum density of (k-1). Building on this, we, for the first time, formalize and comprehensively investigate the historical k-dense subgraph query problem. We propose Online, which identifies k-dense subgraphs in the detemporal graph over the query interval by employing max-flow computation. We then present Online+ and Online++, two corepruning based algorithms that significantly reduce the number of edges requiring max-flow computation. Furthermore, three index structures are developed to support efficient query processing. Specifically, VPI leverages time interval inclusion relationships to achieve significant space savings compared to the naive index storing all k-dense subgraphs for all time intervals, while preserving query performance. TPI refines the structure of VPI to attain optimal query time at the cost of increased space consumption. A compromise index, TUI, reduces space usage while maintaining near-optimal query efficiency by integrating temporal inclusion relationships with the hierarchical nesting of k-dense subgraphs. Additionally, we propose three construction algorithms for VPI: a baseline (BasicVPI) and two optimized variants (BatInsVPI, IncInsVPI). These algorithms are later extended to construct TPI and TUI. The IndexUpdate algorithm for index maintenance is also developed. Extensive experiments and case studies demonstrate the efficiency and effectiveness of our solutions.

源语言英语
主期刊名Proceedings - 2026 IEEE 42nd International Conference on Data Engineering, ICDE 2026
编辑Khuzaima Daudjee, Qiong Luo, Alkis Simitsis
出版商Institute of Electrical and Electronics Engineers Inc.
页1-13
页数13
ISBN(电子版)9798331583651
DOI
出版状态已出版 - 2026
活动42nd International Conference on Data Engineering, ICDE 2026 - Montreal, 加拿大
期限: 4 5月 2026 → …

丛书

姓名Proceedings - 2026 IEEE 42nd International Conference on Data Engineering, ICDE 2026

会议

会议42nd International Conference on Data Engineering, ICDE 2026
国家/地区加拿大
市Montreal
时期4/05/26 → …

学术指纹

探究 'Querying Historical k-Dense Subgraphs on Temporal Graphs' 的科研主题。它们共同构成独一无二的学术指纹。

引用此