计算机工程

作者：杜明, 郝燕, 周军锋, 谭玉婷

单位：东华大学 计算机科学与技术学院, 上海 201620

关键词：时态网络,周期团,时间戳,剪枝策略,最长周期序列,周期长度

基金：国家自然科学基金（61472339，61873337）；上海市自然科学基金（20ZR1402700）。

周期团是在时态网络上出现时机满足特定周期要求的完全子图，周期团挖掘用于挖掘时态图中具有周期性的团。针对现有周期团挖掘方法效率低的问题，设计三种高效的剪枝策略EMP-FlagVex、EMP-FlagEdge和EMP-FlagEdge+，并提出一种基于边上时间戳序列的求解方法EMP。枚举满足要求的极大团，并对枚举出的极大团进行周期验证。验证操作是提取极大团每条边上的时间戳集合，并对集合中出现的时间点进行计数。若某个时间点出现的次数等于提取的集合个数，则将其放入新集合。在此基础上，判断新集合中的序列是否具有周期性。实验结果表明，相比基础方法EMP，将EMP与EMP-FlagEdge+剪枝策略相结合的方法在PS、Lkml、Enron等数据集上的运行时间加快了15倍以上。相比MPC算法，基于顶点度数的EMP-FlagVex剪枝策略的挖掘效率提高约1倍，基于边上时间戳序列长度的EMP-FlagEdge剪枝策略的挖掘效率提高10倍，基于周期子序列长度的EMP-FlagEdge+剪枝策略的挖掘效率提高约30倍。

来源：2023年第4期

《计算机工程》期刊编辑部

查看计算机工程杂志2023年第4期