计算机科学与探索

• 学术研究 •    

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

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

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

Research on Periodic Triangle Enumeration 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:2022-08-10 Published:2022-08-10

摘要: 真实世界中的图通常是时序图,即图中的边具有时间戳,这些时间戳表示边存在的时间。现有大多数图数据挖掘算法只针对静态图。随着图数据挖掘算法和现实需要的发展,时序图的数据挖掘算法开始成为热点问题。其中,周期性是时序数据中一个非常重要的特征。周期性出现的数据通常代表着现实世界中值得关注的行为模式。在静态图的数据挖掘算法中,三角形枚举是一个基础且重要的问题,图中的三角形数量不仅是图的一个基本性质,三角形结构也是很多更为复杂的社群结构的基础,如k-truss。基于时序图,提出了一种新的三角形模型,周期三角形。虽然目前存在一些时序图中周期性社群发现算法的研究,但是这些算法无法高效的枚举图中周期性三角形这种基础的社群结构,也没有考虑到现实世界中图的稀疏性。将周期性数据挖掘与图中的三角形枚举算法相结合,提出了一种高效的时序图周期性三角形枚举算法。实验表明,该算法可以快速的枚举出图中的周期性三角形。

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

Abstract: Real-world graphs are usually temporal graphs, the edges in the graph have timestamps which indicate when these edges exist. Most existing algorithms on graph data mining are designed for static graphs. With the development algorithms on graph data mining and the raise 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. Pattens 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. The number of triangles in a graph is a fundamental property of the graph and triangle is also the basis of many complex community structures, such as k-truss. In this paper, a new triangle model is proposed based on the temporal graph, the periodic triangle. Although there exists some study on periodic community discovery algorithms for temporal graphs, these algorithms cannot efficiently enumerate periodic triangles. They do not take the sparsity of graphs in the real world into account neither. 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. Experiments show that the algorithm proposed in this paper can enumerate periodic triangles in graphs efficiently.

Key words: temporal graph, periodicity, triangle enumeration