Lune

ICDE2024Top-tier venue

Mining Quasi-Periodic Communities in Temporal Network

Yue Zeng, Hongchao Qin, Rong-Hua Li, Kai Wang, Guoren Wang, Xuemin Lin

Abstract

Periodic group behaviors often exist in temporal interaction networks, such as monthly group meetings, quarterly animal migrations, and yearly birthday parties. In real life, these events are usually quasi-periodic, meaning that the time intervals between two adjacent events are nearly constant but not exactly constant. Most existing studies mainly focus on identifying exact periodic group behaviors, which may result in an incomplete detection of periodic patterns in temporal networks. To fill this gap, we focus on a quasi-periodic community mining problem, which aims to find the most representative cohesive sub graphs, including the quasi-periodickk-core and quasi-periodic k-clique. The number of quasi-periodic communities is much larger than that of periodic communities, since the number of quasi-periodic sub-sequences is larger than that of periodic sub-sequences in a given time sequence. To efficiently compute the quasi-periodic communities, we propose a novel two-stage framework. In the first stage, the framework checks whether the time sequence of each vertex contains quasi-periodic sub-sequences. To this end, we develop a new structure, the DAG oracle, which comprises a set of concise DAGs that enables rapid extraction of all quasi-periodic sub-sequences. Based on the DAG oracle, we can easily compute all quasi-periodic sub-sequences for every vertex. In the second stage, the framework computes local quasi-periodic subgraphs that contain the vertex, which allows for the application of existing community mining algorithms. Given the large number of these subgraphs, we propose several carefully -designed pruning rules to further reduce redundant computations. Extensive experiments on 5 real-life datasets demonstrate the efficiency and effectiveness of our proposed solutions.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

1 top-tier paper has cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers1

  1. Efficient Frequency-Aware k-Core Query on Temporal GraphsZhongfan Du, Ming Zhong, Yuanyuan Zhu, Tieyun Qian et al.ICDE 2025

Builds on3

  1. Distributed D-core Decomposition over Large Directed GraphsXuankun Liao, Qing Liu, Jiaxin Jiang, Xin Huang et al.VLDB 2022 · 32 citations
  2. Fast Maximal Clique Enumeration on Uncertain Graphs: A Pivot-based ApproachQiangqiang Dai, Rong-Hua Li, Meihao Liao, Hongzhi Chen et al.SIGMOD 2022 · 22 citations
  3. Fairness-aware Maximal Clique EnumerationMinjia Pan, Rong-Hua Li, Qi Zhang, Yongheng Dai et al.ICDE 2022 · 15 citations

Related papers

  1. Periodic Community Search in Temporal Graphs: Time Series-based MethodsYu Chen, Qing Liu, Chengyang Luo, Yunjun GaoSIGMOD 2026
  2. Scaling Up k-Clique Percolation Community DetectionYue Zeng, Miao Qiao, Rong-Hua Li, Hongchao Qin et al.SIGMOD 2026 · 1 citation
  3. Scalable Mining of Maximal Quasi-Cliques: An Algorithm-System Codesign ApproachGuimu Guo, Da Yan, M. Tamer Özsu, Zhe Jiang et al.VLDB 2021 · 30 citations
  4. Optimal Quasi-clique: Hardness, Equivalence with Densest-k-Subgraph, and Quasi-partitioned Community MiningAritra Konar, Nicholas D. SidiropoulosAAAI 2024 · 6 citations
  5. Maximal Directed Quasi -Clique MiningGuimu Guo, Da Yan, Lyuheng Yuan, Jalal Khalil et al.ICDE 2022 · 23 citations
Dusk over the sea between two cliffs drawn in fine vertical lines