一种高效的周期团挖掘方法

摘要：

周期团是在时态网络上出现时机满足特定周期要求的完全子图,周期团挖掘用于挖掘时态图中具有周期性的团.针对现有周期团挖掘方法效率低的问题,设计三种高效的剪枝策略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倍.

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

所属期刊栏目：49

分类号：TP391(计算技术、计算机技术)

资助基金：国家自然科学基金;国家自然科学基金;上海市自然科学基金

在线出版日期：2023-04-19（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：68-76