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

来源：计算机科学与探索杂志2023年第8期北京时间：

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

单位：1. 北京理工大学 计算机学院，北京 1000812. 电科云（北京）科技有限公司，北京 100041

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

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