-
题名一种高效的周期团挖掘方法
- 1
-
-
作者
杜明
郝燕
周军锋
谭玉婷
-
机构
东华大学计算机科学与技术学院
-
出处
《计算机工程》
CAS
CSCD
北大核心
2023年第4期68-76,共9页
-
基金
国家自然科学基金(61472339,61873337)
上海市自然科学基金(20ZR1402700)。
-
文摘
周期团是在时态网络上出现时机满足特定周期要求的完全子图,周期团挖掘用于挖掘时态图中具有周期性的团。针对现有周期团挖掘方法效率低的问题,设计三种高效的剪枝策略EMP-FlagVex、EMP-FlagEdge和EMPFlagEdge+,并提出一种基于边上时间戳序列的求解方法EMP。枚举满足要求的极大团,并对枚举出的极大团进行周期验证。验证操作是提取极大团每条边上的时间戳集合,并对集合中出现的时间点进行计数。若某个时间点出现的次数等于提取的集合个数,则将其放入新集合。在此基础上,判断新集合中的序列是否具有周期性。实验结果表明,相比基础方法EMP,将EMP与EMP-FlagEdge+剪枝策略相结合的方法在PS、Lkml、Enron等数据集上的运行时间加快了15倍以上。相比MPC算法,基于顶点度数的EMP-FlagVex剪枝策略的挖掘效率提高约1倍,基于边上时间戳序列长度的EMP-FlagEdge剪枝策略的挖掘效率提高10倍,基于周期子序列长度的EMP-FlagEdge+剪枝策略的挖掘效率提高约30倍。
-
关键词
时态网络
周期团
时间戳
剪枝策略
最长周期序列
周期长度
-
Keywords
temporal network
periodic cliques
timestamp
pruning strategy
longest period sequence
period length
-
分类号
TP391
[自动化与计算机技术—计算机应用技术]
-
