Mining Quasi-Periodic Communities in Temporal Network

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

*此作品的通讯作者

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

摘要

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-periodic k-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.

源语言英语
主期刊名Proceedings - 2024 IEEE 40th International Conference on Data Engineering, ICDE 2024
出版商IEEE Computer Society
2476-2488
页数13
ISBN(电子版)9798350317152
DOI
出版状态已出版 - 2024
活动40th IEEE International Conference on Data Engineering, ICDE 2024 - Utrecht, 荷兰
期限: 13 5月 202417 5月 2024

出版系列

姓名Proceedings - International Conference on Data Engineering
ISSN(印刷版)1084-4627
ISSN(电子版)2375-0286

会议

会议40th IEEE International Conference on Data Engineering, ICDE 2024
国家/地区荷兰
Utrecht
时期13/05/2417/05/24

指纹

探究 'Mining Quasi-Periodic Communities in Temporal Network' 的科研主题。它们共同构成独一无二的指纹。

引用此

Zeng, Y., Qin, H., Li, R. H., Wang, K., Wang, G., & Lin, X. (2024). Mining Quasi-Periodic Communities in Temporal Network. 在 Proceedings - 2024 IEEE 40th International Conference on Data Engineering, ICDE 2024 (页码 2476-2488). (Proceedings - International Conference on Data Engineering). IEEE Computer Society. https://doi.org/10.1109/ICDE60146.2024.00195