计算机科学与探索 ›› 2023, Vol. 17 ›› Issue (8): 1833-1841.DOI: 10.3778/j.issn.1673-9418.2202004

• 理论·算法 • 上一篇    下一篇

面向时序图的周期性三角形枚举算法研究

任泽槟,李荣华,戴永恒,王国仁   

  1. 1. 北京理工大学 计算机学院,北京 100081
    2. 电科云(北京)科技有限公司,北京 100041
  • 出版日期:2023-08-01 发布日期:2023-08-01

Research on Periodic Triangle Enumeration Algorithm for Temporal Graphs

REN Zebin, LI Ronghua, DAI Yongheng, WANG Guoren   

  1. 1. School of Computer Science & Technology, Beijing Institute of Technology, Beijing 100081, China
    2. Diankeyun Technologies Co., Ltd., Beijing 100041, China
  • Online:2023-08-01 Published:2023-08-01

摘要: 真实世界中的图通常是时序图,即图中的边具有时间戳。随着图数据挖掘算法和现实需要的发展,时序图的数据挖掘算法开始成为热点问题。其中,周期性是时序数据中一个非常重要的特征。周期性出现的数据通常代表着现实世界中值得关注的行为模式。在静态图的数据挖掘算法中,三角形枚举是一个基础且重要的问题。基于时序图,提出了一种新的三角形社群模型,周期三角形,并将周期性数据挖掘与图中的三角形枚举算法相结合,提出了一种高效的时序图周期性三角形枚举算法。该算法主要包含三部分:高效的多级剪枝算法,该算法可以在较小的时间代价下删除不在任何周期三角形中的顶点和边;极大周期枚举算法,通过计算极大周期,提出的算法可以避免对时间维度上重叠社群进行重复枚举;边枚举边剪枝的高效的周期三角形枚举算法。实验表明,该算法可以快速枚举出图中的周期性三角形。

关键词: 时序图, 周期性, 三角形枚举

Abstract: Real-world graphs are usually temporal graphs, and their edges are associated with timestamps. With the development of algorithms on graph data mining and the increase of needs in real-world, data mining algorithms for temporal graphs have started to become a hot topic. Periodicity is a very important feature in temporal data. Patterns that occur periodically in real world usually indicate important features. In data mining algorithms for static graphs, triangle enumeration is a fundamental and important problem. In this paper, a new triangle model is proposed based on the temporal graph, the periodic triangle. In this paper, periodic data mining is combined with triangle enumeration algorithms in graphs, and an efficient algorithm for periodic triangle enumeration in temporal graphs is proposed. This algorithm contains three components: the first one is an efficient multi-level pruning algorithm which can delete vertices and edges which are not in any periodic triangle at low cost; the second one is a maximal periodic enumeration algorithm that can avoid enumeration on overlapping communities in time axis; the third one is an efficient periodic triangle enumeration algorithm that prunes unnecessary vertices and edges while enumeration. Experiments show that the algorithm proposed in this paper can enumerate periodic triangles in graphs efficiently.

Key words: temporal graph, periodicity, triangle enumeration