科研之友
微信
新浪微博
Facebook
分享链接
摘要
周期团是时态网络上出现时机满足特定周期要求的完全子图，周期团挖掘是时态图上一种基础操作，用于挖掘时态图中具有周期性的团。针对现有方法效率低的问题，本文提出一种基于边上时间戳序列的求解方法，其基本思想是先枚举后验证。该方法首先枚举满足要求的极大团，然后对枚举出的极大团进行周期验证。验证操作是将极大团每条边上的时间戳集合提取出来，并对集合中出现的时间点进行计数。若某个时间点出现的次数等于提取的集合个数则将其放入新集合，最后判断新集合中的序列是否具有周期性。实验证明在大多数数据集上，该方法比已有方法快了将近1.2倍，在少数几个数据集上，快了将近6倍，有的甚至在15倍以上。本文基于该方法提出三种高效的剪枝策略来缩小原图，分别是将挖掘效率提高1倍左右的基于顶点度数的EMP-FlagVex剪枝策略，将挖掘效率提高10倍左右的基于边上时间戳序列长度的EMP-FlagEdge剪枝策略，将挖掘效率提高30倍左右的基于周期子序列长度的EMP-FlagEdge+剪枝策略。最后，在10个真实数据集上进行实验测试，实验结果验证了本文所提出方法和剪枝策略的高效性。
- 单位
