一种高效的周期团挖掘方法_杜明.pdf

第 49卷 第 4期2023年 4月Computer Engineering 计算机工程一种高效的周期团挖掘方法杜明，郝燕，周军锋，谭玉婷（东华大学 计算机科学与技术学院，上海 201620）摘要：周期团是在时态网络上出现时机满足特定周期要求的完全子图，周期团挖掘用于挖掘时态图中具有周期性的团。针对现有周期团挖掘方法效率低的问题，设计三种高效的剪枝策略 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倍。关键词：时态网络；周期团；时间戳；剪枝策略；最长周期序列；周期长度开放科学（资源服务）标志码（OSID）：中文引用格式：杜明，郝燕，周军锋，等.一种高效的周期团挖掘方法 J.计算机工程，2023，49（4）：68-76.英文引用格式：DU M，HAO Y，ZHOU J F，et al.An efficient method for mining periodic cliques J.Computer Engineering，2023，49（4）：68-76.An Efficient Method for Mining Periodic CliquesDU Ming，HAO Yan，ZHOU Junfeng，TAN Yuting（School of Computer Science and Technology，DongHua University，Shanghai 201620，China）【Abstract】Periodic cliques are complete subgraphs that meet specific periodic requirements when they appear on the temporal network.Periodic cliques mining is used to mine periodic cliques in the temporal graph.Considering the low efficiency of the existing periodic cliques mining methods，three efficient pruning strategies EMP-FlagVex，EMP-FlagEdge，and EMP-FlagEdge+are designed，and a solution method based on the edge timestamp sequence EMP is proposed.Enumerate the maximum cliques that meet the requirements，and periodically verify the maximum cliques listed.The verification operation involves extracting the timestamp set on each side of the maximum cliques and counting the time points that appear in the set.If the number of occurrences of a time point is equal to the number of extracted sets，it will be placed in a new set.On this basis，it can be judged whether the sequence in the new set is periodic.The experimental results show that the running time of the method combining EMP with EMP-FlagEdge+pruning strategy on PS，Lkml，Enron and other data sets is approximately 15 times faster than the basic method EMP.Compared with the MPC algorithm，the mining efficiency of the EMP-FlagVex pruning strategy based on vertex degree is approximately 1 time higher，the EMP-FlagEdge pruning strategy based on the length of the timestamp sequence on the edge is 10 times higher，and the EMP-FlagEdge+pruning strategy based on the length of the periodic subsequence is approximately 30 times higher.【Key words】temporal network；periodic cliques；timestamp；pruning strategy；longest period sequence；period lengthDOI：10.19678/j.issn.1000-3428.00641920概述 时态网络是边上带有时间信息的网络1-3，用于表示顶点间与时间相关的各种约束关系。例如，在面对面的接触网络中4-6，每条边（u，v，t）表示两个个体u和v在t时刻有联系。在电子邮件通信网络中，每封电子邮件都包含一个发送者和一个接收者，以及发送电子邮件的时间。在科学协作网络中，每条边（u，v，t）表示两个作者 u和 v在时间 t共同完成一篇论文。基金项目：国家自然科学基金（61472339，61873337）；上海市自然科学基金（20ZR1402700）。作者简介：杜明（1975），男，副教授、博士，主研方向为自然语言处理、信息查询、数据分析；郝燕（通信作者），硕士研究生；周军锋，教授、博士、博士生导师、CCF会员；谭玉婷，博士。收稿日期：2022-03-16 修回日期：2022-05-19 Email：人工智能与模式识别文章编号：1000-3428（2023）04-0068-09 文献标志码：A 中图分类号：TP391第 49卷 第 4期杜明，郝燕，周军锋，等：一种高效的周期团挖掘方法周期团7是时态网络上出现时机满足特定周期要求的完全子图，其任意两个顶点都有边连接。周期团挖掘对于理解和预测时态网络中的群体行为是非常重要的。例如，在 Dblp 科学写作网络中，A、B、C、D 这 4 位作者在某段时间共同合作撰写论文，可以将其建模为一个含有时间信息的时态网络。这4位作者在 20192021年进行相互协作，则组成的社区具有周期性，能够预测 4 位作者将在 2022 年再次合作。QIN 等7提出现有的周期团挖掘方法，设计剪枝+求解的 MPC（Mining Periodic Cliques）算法来求解周期团，但是该算法在剪枝和求解两个阶段都存在效率低、重复计算等问题。在剪枝阶段，MPC 算法需要多次遍历图中的顶点和边并判断其是否具有符合条件的周期序列，以删除不满足周期性要求的顶点和边。在求解阶段，MPC 算法使用图转换的方法求解周期团，图转化即从剪枝后的时态图中导出具有相同周期的子图，分别在不同子图上求解满足规模要求的团。在图转化阶段，该算法需要重新计算顶点的周期，增加了计算量。同一个时态图在图转换之后可能生成多个子图，使得枚举图规模增大，导致枚举效率降低。本文设计 3 种高效的剪枝策略 EMP-FlagVex、EMP-FlagEdge、EMP-FlagEdge+，以缩小原时态图的规模，避免后续的挖掘算法对图中不满足条件的顶点进行访问，显著提升算法的整体性能。基于所提的剪枝策略，提出一种在时态网络中有效枚举所有极大周期团的方法 EMP。通过枚举极大团，再对所枚举的极大团进行验证，避免图转化产生计算量以及枚举图规模变大的可能性。1背景知识与相关工作 1.1背景知识给定时态图 G=（V，E），其中，V 表示时态图中顶点的集合，E 表示时态图中边的集合，时态图中的每条边 eE 是一个三元组（u，v，t）。三元组（u，v，t）表示 u到 v这条边在 t时刻出现。令 n|V|，m|E|，n和m分别表示时态图顶点的数量和边的数量。定义1（团8-10）在图G=（V，E）中，如果在顶点子集 C 中任意顶点之间都有边相连，则顶点子集 C 是一个团。定义 2（极大团8-10）对于图 G=（V，E）中的顶点子集MV，满足以下条件：1）M满足团的定义；2）不存在一个顶点uuM，使得Mu是一个团，则M是一个极大团。定义3（K-团8-10）在时态图G=（V，E）中，如果顶点子集 CV，满足 2个条件：1）C是一个团；2）|V（c）|=K，则 C是一个 K-团。定义4（周期团7）在时态图G=（V，E）中，如果顶点子集CV，满足以下2个条件：1）C是一个团；2）C存在一个周期序列 T（e），则 C可称为周期团。定义 5（-周期团7）在时态图 G=（V，E）中，如果顶点子集 CV，满足以下 3个条件：1）C是一个团；2）C是一个周期团；3）|T（e）|=，则 C是-周期团。定义 6（，K）-周期团7）在时态图 G=（V，E）中，如果顶点子集 CV，满足以下 3个条件：1）C是一个团；2）C 是一个周期团；3）|T（e）|=，|V（c）|=K，则 C是一个（，K）周期团。定义 7 给定时态图 G=（V，E）和参数值、K，枚举图 G中所有的极大（，K）-周期团。1.2相关工作团的挖掘主要分为在非时态网络上的挖掘和在时态网络上的挖掘。1）在非时态网络上的挖掘方法现有的非时态图上团挖掘算法主要有基于确定图11-15的枚举算法16-18和基于不确定图19-23的枚举算法24-26。本文是在确定图上进行挖掘，只介绍基于确定图的枚举算法。基于确定图的枚举算法主要是 BK算法。BK算法的基本形式是一种递归回溯算法。总体上，给定3个不相交的顶点集 R、P、X，该算法找到包含 R中的所有顶点，P 中的某些顶点和不在 X 中顶点的极大团。在 BK 算法的每次调用中，P 和 X 是不相交的集合，它们的并集由添加到 R 时形成团的那些顶点组成，即 PX 是连接到 R 每个元素的一组顶点。当 P和 X 都为空时，没有其他元素可以添加到 R，因此，R是极大团，算法输出 R。2）在时态网络上的挖掘方法现有关于时态网络上的挖掘算法比较少，对于时态网络的研究主要有张天明等27提出的时态图最短路径查询方法、陈东明等28提出的时态网络节点相似性度量及链路预测算法以及程开原等29提出的时态网络中知识图谱推荐：关键技术与研究进展。关 于 时 态 网 络 上 周 期 团 的 研 究 主 要 有 HIMMEL等30提出将 BK算法应用在时态图上的极大团枚举，QIN等7提出的时态网络中周期团挖掘，主要用于挖掘时态网络中具有周期性的社区。文献 7 提出时态网络中周期团挖掘问题。剪枝过程示例如图 1所示。在图 1（a）所示的时态图上求解周期长度为 3，顶点规模为 4 的周期团。首先，遍历图中所有顶点并计算其周期，顶点 v8的周期为 1，2，不满足条件，被删除。然后，与 v8相连接的顶点 v1、v4、v7的周期性须图 1剪枝过程示例Fig.1Example of pruning process692023年 4月 15日Computer Engineering 计算机工程重新计算，此时 v7的周期由 1，2，3 变为 1，2，不满足条件，被删除。当 v7被删除后，与其相连接的顶点v4、v5、v6的周期性须重新计算。当处理完顶点后，接着遍历图中所有边并计算其周期，边（v4，v5）的时间戳为1，2，5，不满足条件，被删除。此时的顶点 v4已被重复计算 4 次，其周期未改变。一直重复上述操作，直到图中所有的顶点和边都满足条件，得到如图 1（b）所示的结果。针对该剪枝方法存在的不足，本文提出新的剪枝策略。该剪枝策略只需要将不满足大小及周期阈值要求的顶点和边删除，其原因为本文所提的求解方法不需要在周期图上操作。同样地，对于图 1（a）所示的时态图求解周期长度为 3，顶点规模为 4的周期团，本文算法首先删除边（v1，v8）和边（v4，v8），在边（v1，v8）和边（v4，v8）上的时间戳序列长度小于 3，边（v4，v7）上时间戳序列长度为 3，但没有满足阈值的周期序列。当删除这 3 条边后 v8的度变为 1，将其删除，此时 v7、v6、v5因 v8的删除不再满足团规模要求，将其全部删除。经过上述操作后即可得到如图 1（b）所示的结果，该过程不存在重复计算的问题。将图1（b）所示的周期图进行转化，先计算顶点的周期，再将具有相同周期的顶点相连接。图转化方法示意图如图2所示，图2（b）和图2（c）所示为2个子图的示意图。对图2（b）所示的时态子图，MPC算法需要在图2（b）和图2（c）所示的转换后顶点规模为6的时态图上进行枚举操作，而本文算法只需要在图2（b）所示的顶点规模为 4的时态图上进行操作。2EMP算法 2.1EMP算法思想该算法首先找到图中满足条件的极大团，然后判断该团是否为周期团，即判断每条边是否存在相同的周期序列。因此，本文从边上的时间戳集合着手，提取该极大团所有边上的时间戳集合和该集合中对应的时间并计数。若某个时间出现的次数与提取的时间戳集合个数相等，说明每条边都会出现在这个时间，如果这些时间呈现周期规律，那么该团就是周期团。求解过程示例如图 3所示。图 3（a）所示为时态图，给定 K=4，=4。首先，枚举图 3（b）所示的 4-团，然后，提取图 3（b）的 4-团边上的时间戳集合并计数，得到集合个数 sum=6，对集合中的时间进行计数得到结果：即 T1=6、T2=1、T3=6、T5=6、T7=6、T9=5，时间出现次数与集合个数相等的时间有1，3，5，7。集合1，3，5，7 是一个长度为 4 的周期序列，则该 4-团是一个（4，4）-周期团。在验证阶段有一个特殊情况，即验证的极大团不是周期团，但其子团是周期团的情况，这种情况采用枚举的方法进行再挖掘。枚举过程示例如图4所示。4-团示例如图 4（a）所示，若要求规模为 3、长度为 4的周期团，将图 4（a）所示的 4-团进行枚举，得到如图 4（b）、图4（c）、图4（d）和图4（e）所示的4个3-团，只有图4（c）的团周期1，3，5，7为周期性序列且长度为 4，满足要求。2.2EMP-FlagVex剪枝策略根据定义 1和定义 3，任何一个属于（，K）-周期团的顶点 v，它的度为 K1。EMP-FlagVex 剪枝策略将图中所有度小于 K1的顶点全部删除得到新的时态图 G1。EMP-FlagVex的两个重要属性见引理 1、定理 1，将用于在枚举所有周期团时进行剪枝。引理 1 任何一个属于（，K）-周期团的顶点一定包含在 EMP-FlagVex剪枝后的时态图中。证明 假设存在一个顶点属于（，K）-周期团，但是不包含EMP-FlagVex剪枝后的时态图中，（，K）-周期团顶点的度为 K1，而不包含在 EMP-FlagVex剪枝后的时态图中顶点的度小于 K1，相互矛盾。定理1 给定一个时态图G，参数K，如果存在EMP-FlagVex剪枝后的时态图，那么时态图 G中必是唯一。证明 假设EMP-FlagVex剪枝后的时态图不唯一，即存在另一个时态图。在该时态图中具有EMP-FlagVex剪枝后的时态图不存在的顶点或者没有EMP-FlagVex剪枝后的时态图中存在的顶点。在不存在EMP-FlagVex剪枝后时态图中的顶点度小于 K1，并且没有 EMP-FlagVex 剪枝后时态图中存在的顶点都是与 EMP-图 2图转化方法示意图Fig.2Schematic diagram of the graph transformation method图 3求解过程示例Fig.3Example of solution process图 4枚举过程示例Fig.4Example of enumeration process70第 49卷 第 4期杜明，郝燕，周军锋，等：一种高效的周期团挖掘方法FlagVex 剪枝策略的约束条件相矛盾。因此，EMP-FlagVex剪枝后的时态图是时态图G中唯一的时态图。本文基于引理 1和定理 1，首先计算原始时态图G 中的 G1，然后在时态图 G1上进行周期团的挖掘。对于任意的顶点 uG，如果存在于 K-团中，其度必须为 K1。因此，若要挖掘（，K）-周期团，度小于 K1的顶点不满足条件，根据这个原则将不满足要求的顶点进行预删除，从而缩小原图规模。算法 1 EMP-FlagVex输入 时态图 G，变量 K输出 新时态图 G11.for u in G puter the degree of u in G3.if degree（u）K1 then4.mapDelete（u）&Q.push（u）/记录不符合要求的结点5.while（！Q.empty（）do6.Q.pop（u）7.for wNu（G）do/w是结点 u的邻居结点8.swap（w，u）.index/交换结点 w、u的角下标9.degree（w）-10.if degree（w）K1 then11.mapDelete（w）&Q.push（w）12.G1=G13.return G1算法1首先计算每个顶点的度（步骤1和步骤2），如果顶点的度不符合给定参数要求，对其进行标记，并且压入队列中（步骤 3和步骤 4），如果队列不为空，取出队列中的第一个元素（步骤 5和步骤 6），更新与之相连接顶点的度，并且将边的角下标进行交换（步骤 79），如果与之相连接顶点的度在更新后，度不符合给定参数要求，将其压入队列中（步骤10和步骤11），重复上述操作，直到队列为空则结束操作。将剪枝后的图赋给新的时态图，返回新的时态图（步骤 12和步骤 13）。例 1 本文考虑图 3（a）的无向时态图，根据给定值 K=3，度小于 K1 的顶点将被删除。从图 3（a）可以看出：v7的度为 2 被删除，与 v7相邻的顶点度自减1，v6的度由 3 变为 2，v4的度由 6 变为 5，删除 v6，重复上述操作最后得到 EMP-FlagVex 剪枝结果，其示意图如图 5所示。算法 1 首先从头到尾遍历一遍顶点，寻找不满足条件的顶点并进行 bfs 遍历，总的时间复杂度为O（m+bfs），m 为顶点数，空间复杂度就是 bfs 遍历所用的队列。在 bfs 整个过程中只计算需要删除多少条边（对此计数），队列和 mapDelete从头到尾只有删除顶点的信息。因此，bfs 的时间复杂度为O(n)，n为删边数，空间复杂度为O(2m)，m为删除顶点数。整个 EMP-FlagVex 的时间复杂度为O(m+n)，空间复杂度为O(2m)。定理 2 算法 1能正确地计算 G1。证明 设 S=VcD，显然，对于算法 1，S 中的每个顶点都是通过剪枝后满足（，K）-周期团条件的顶点。为证明 S 就是 G1，假设存在一个集合S，使得：1）S中的每个顶点都是通过剪枝后满足（，K）-周期团条件的顶点；2）SS，因 SS，存在一个属于（，K）-周期团的顶点 uSS。根据本文假设，S 中的每个顶点在剪枝后都具有不小于 K 的度数。因此，算法 1不能删除顶点 u，这与 uVcD相矛盾。2.3EMP-FlagEdge剪枝策略虽然EMP-FlagVex可以剪枝掉许多不满足条件的顶点，但是它对于剪枝边不是很有效。例如，在图3（a）中，如果给定=4，那么边（v5，v6）和边（v4，v5）明显是不满足条件的，因为其时间戳序列长度为 3，边（v4，v7）的时间戳序列长度虽然为4，但非周期序列。因此，该边不能包含在（，K）-周期团中。为解决该问题，本文提出一种新的剪枝策略 EMP-FlagEdge。根据定义 5和定义 6可知，任何一个属于（，K）-周期团的边 e，其边上时间戳存在长度为 的周期序列。剪枝策略 EMP-FlagEdge 将图 5 中时间戳长度小于等于 但非周期序列的边全部删除，得到新的时态图 G2。引理 2 任何一个属于（，K）-周期团的边都一定包含在 EMP-FlagEdge剪枝后的时态图中。证明 假设存在一条边属于（，K）-周期团，但不包含在 EMP-FlagEdge 剪枝后的时态图中，属于（，K）-周期团的边的时间戳长度等于，并且是周期序列，而不包含在 EMP-FlagEdge剪枝后的时态图中 的 边，其 长 度 小 于 并 且 是 非 周 期 序 列，相 互矛盾。定理 3 给定一个时态图 G，参数 和参数 K，如果存在 EMP-FlagEdge剪枝后的时态图，那么必是时态图 G中的唯一时态图。证明 假设 EMP-FlagEdge 剪枝后的时态图不唯一，即存在另一个时态图，该时态图中具有 EMP-FlagEdge 剪枝后的时态图中不存在的边或者没有EMP-FlagEdge 剪枝后的时态图中存在的边。在不存在 EMP-FlagEdge 剪枝后的时态图中的边时间戳长度小于，并且没有 EMP-FlagEdge 剪枝后的时态图中存在的边都是与 EMP-FlagEdge 剪枝策略的约束条件相矛盾。因此，EMP-FlagEdge剪枝后的时态图是时态图 G中唯一的时态图。本文基于引理 2和定理 3，首先剪枝掉不满足条件的边，然后在缩减的图上枚举所有的（，K）-周期团。图 5EMP-FlagVex剪枝结果示意图Fig.5Schematic diagram of EMP-FlagVex pruning results712023年 4月 15日Computer Engineering 计算机工程算法 2 EMP-FlagEdge输入 时态图 G1，变量，变量 K输出 时态图 G21.for（u，v）in G1 do 2.while timeStamp.size（）|timeStamp.size（）=&！has（timeStamp）do/timeStamp.size（）是指时间戳长度，has是/判断时间戳序列是否为周期性序列函数。3.edgeDelete（u，v）4.degree（u）-5.if degree（u）K1 then6.mapDelete（u）&Q.push（u）/标记不符合要求结点 u/并将其放入队列7.while（！Q.empty（）do8.Q.pop（u）9.for wNu（G1）do/w是结点 u的邻居结点10.degree（w）-11.if degree（w）K1 then12.mapDelete（w）&Q.push（w）/标记不符合要求结点/w并将其放入队列13.G2=G114.return G2算法 2 首先判断边上的时间戳序列是否符合条件（步骤 1和步骤 2），对不符合条件的时间戳序列进行标记，并且与边集最后一个时间戳序列进行交换（步骤 3和步骤 4），在删除的边中两端的顶点度自减1（步骤 512），最后采用算法 1对相应顶点度进行判断，将更新后的图赋给新的时态图，最后返回结果（步骤 13和步骤 14）。例 2 考虑如图 5所示无向图，给定参数=4，K=3。从图5可以看出：在（v4，v5）这条边上的时间戳长度为3，小于给定值，将其删除，得到的结果如图6所示。算法 2的时间复杂度是（|V|+|E|+|T|2），其中，V 是顶点数，E 是删除的边数，T 是每条边时间戳数组长度。算法 2 的空间复杂度是（|E|+|V|+|T|），其中，E是边数，V 是删除的顶点数，|T|是每条边的时间戳数组长度的加和（因为需要判断时间戳数组是否等差）。定理 4 算法 2能正确地计算出 G2。证明 设 S=E（u，v）ED，显然，对于算法 2，S中的每条边都是通过剪枝后满足（，K）-周期团条件的边。为证明S就是G2，假设存在一个集合S，使得：1）S中的每条边都是通过剪枝后满足（，K）-周期团条件的边；2）SS，由于SS，因此存在一个属于（，K）-周期团的边（u，v）SS。根据本文假设，S中的每条边在剪枝后都具有不小于的时间戳长度。因此，算法2不能删除边（u，v），这与边（u，v）E（u，v）ED相矛盾。2.4EMP-FlagEdge+剪枝策略EMP-FlagEdge剪枝策略存在一个问题，若边上时间戳长度足够长，但是不存在周期序列或者其存在的最大周期子序列长度不满足阈值。例如，1，2，5，7，8这个时间戳序列，其长度为 5，但存在的最大周 期 子 序 列 长 度 只 有 2。因 此，本 文 进 一 步 提 出EMP-FlagEdge+剪枝策略。定义 8（最长等差数列长度）给定一个数组，在这个数组中存在若干等差子数列，其中，长度最长的称为最长等差数列，其长度称为最长等差数列长度。例如，在数组20，1，15，3，10，5，8中存在最长的等差子数列为 20，15，10，5，其长度为 4。根据定义 8，任何一个属于（，K）-周期团的边 e，其边上的时间戳存在长度为 的周期序列。EMP-FlagEdge+剪枝策略将全部删除图中边上时间戳存在的长度小于 最长周期子序列，得到新时态图 G3。引理 3 任何一个属于（，K）-周期团的边都必须包含在 EMP-FlagEdge+剪枝后的时态图中。证明 假设存在一条边属于（，K）-周期团，但不包含在 EMP-FlagEdge+剪枝后的时态图中，属于（，K）-周期团的边，其时间戳为周期 的周期序列，而包含在 EMP-FlagEdge+剪枝后时态图中的边，存在的周期序列长度小于，相互矛盾。定理 5 给定一个时态图 G，参数 和参数 K，如果存在 EMP-FlagEdge+剪枝后的时态图，那么必是时态图 G中唯一的时态图。证明 假设EMP-FlagEdge+剪枝后的时态图不唯一，即存在另一个时态图。在该时态图中具有 EMP-FlagEdge+剪枝后的时态图中不存在的边或者没有EMP-FlagEdge+剪枝后的时态图中存在的边。在不存在EMP-FlagEdge剪枝后的时态图中的边时间戳的最长周期序列长度小于，并且没有EMP-FlagEdge剪枝后时态图中存在的边都是与EMP-FlagEdge+剪枝策略的约束条件相矛盾。因此，EMP-FlagEdge+剪枝后的时态图是时态图 G中唯一的时态图。EMP-FlagEdge+剪 枝 策 略 是 在 EMP-FlagEdge基础上进行操作，针对 EMP-FlagEdge 存在的问题，EMP-FlagEdge+算法提出最长周期子序列长度（最长等差数列长度）新概念，若该边的时间戳存在最长周期序列长度小于，将其删除。算法 3 EMP-FlagEdge+输入 时态图 G2，变量，变量 K输出 时态图 G31.for u in G2 do 2.if u.degree=0|mapDelete.count（u）then/如果结点 u的顶点度为 0或者是被标记的，则结束操作3.continue图 6EMP-FlagEdge剪枝结果示意图Fig.6Schematic diagram of EMP-FlagEdge pruning results72第 49卷 第 4期杜明，郝燕，周军锋，等：一种高效的周期团挖掘方法4.for rNu（G2）do5.while longestArithSeqLength（u，r）adjList u.adjvex r）then9.timeStamp.first 0=r10.else11.timeStamp.first 1=r/将角下标进行更新12.u.degree-13.if u.degree K1 then14.mapDelete（u）=115.break16.G3=G217.return G3算法 3首先遍历顶点，如果遇到被标记的点或者度为 0的顶点，则直接跳过（步骤 13），判断该边的时间戳序列是否满足要求，调用最长周期序列长度算法求解出每条边上时间戳序列的最长周期序列长度。如果边上时间戳集合序列的最大长度周期序列的长度小于给定值，则标记这条边，并将其边表所在的位置与边表最后位置对调，表示这条边将被删除（步骤411）。由于删除边会对该边顶点的度产生影响，因此需要对该边的 2个顶点的度进行更新操作，更新后利用算法 3步骤 1所讲解的方法来判断该顶点的度还是否符合给定参数要求（步骤 1215），如果不符合要求，将其删除。重复上述操作，直到时态图中的所有边都符合给定参数要求后，结束操作，将剪枝后的时态图赋给新时态图，最后返回结果（步骤16和步骤17）。例 3 考虑图 6 所示的图，给定=4，K=4，计算在每条边上的时间戳最长周期序列的长度，不满足条件的边有（v1，v4）、（v2，v4）、（v3，v4），将其删除。此时，v4的度变为 0 不满足参数要求，将其删除。操作结束后得到如图 3（b）所示的结果。算法 4 EMP输入 时态图 G3，变量，变量 K输出 周期团数量1.for u in G3 do 2.may_mc.push_back（u）/may_mc表示可能加入极大团/的结点集合3.Bron-Kerbosch（now_mc，may_mc，done_mc，G3）/now_mc表示当前加入极大团结点集合，done_mc表示已经/加入极大团结点集合4.for（i，j）in now_mc do/计算极大团边数。5.sum+6.for l in timeStamp do/timeStamp表示时间戳序列。7.if（m.end（）！=m.find（x l）then/用 map 迭代器对/边上时间戳序列的时间点进行计数8.m timeStamp l +9.else10.m.insert（pair（x l，1）11.for t in m do/t表示时间点12.if t.second=sum then 13.dc.push_back/若时间点的数量符合要求，将其放入/新数组中14.if has（dc）&dc.size（）=then 15.+maximal_cliques/若新数组满足要求，则周期团数/量加 116.else 17.SpecialEnum（now_mc）/否则调用特殊枚举函数进行/枚举18.return maximal_cliques 算法 4 中的先进性极大团枚举操作，将所有的顶点放入 may_mc（）集合中（步骤 1 和步骤 2），调用BK算法求出符合要求的极大团（步骤 3）。提取在极大团边上的时间戳序列并计数（步骤 46），对每条边上时间戳序列出现的时间点进行计数（步骤 711），若某个时间点出现的次数与时间戳序列的数量相等，将其放入新数组（步骤 12和步骤 13）。对新数组进行周期性判断（步骤 14）。如果该团为符合条件的周期团，则周期团数量加 1（步骤 15）。如果不是符合条件的周期团，则调用算法 3 的步骤 2 判断其子团是否为符合条件的周期团，最后返回周期团数量（步骤 1618）。因此，EMP算法的空间复杂度为 O（|V|+|E|+|E|+|T|），其中，V为删除顶点数，E 为边数，E为删边数，|T|为每条边时间戳数组长度总和。时间复杂度为 O（|V|+|E|+|T|21），其中，|V|是顶点数，E是删除的边数，|T|为时间戳数组长度，为求解周期长度。3实验结果与分析 3.1实验环境在实验中，本文利用新的算法EMP来挖掘极大（，K）-周期团，将基础算法与3个剪枝策略相结合来提高挖掘效率。其中：EMP-O表示基础算法 EMP，首先使用BK算法进行极大团枚举，然后利用边上时间戳进行验证；EMP-FV表示 EMP算法与 EMP-FlagVex剪枝策略相结合；EMP-FE表示EMP算法与EMP-FlagEdge剪枝 策 略 相 结 合；EMP-FE+表 示 EMP 算法与 EMP-FlagEdge+剪枝策略相结合。本文实验所用的硬件平台是Inter Core i5主频为2.50 GHz的CPU，8 GB的RAM内存，操作系统为 Windows10 64位的系统。实验的运行环境为 Code Block 13.12，算法均采用 C+语言实现。3.2数据集本文所使用的数据集为 10 个真实数据集，符号|V|和|E|分别表示时态图中的顶点数量和边的数量，这些数据源自生活中的不同领域，其中都蕴含着时间信息，适合利用时态网络图来存储表示。数据集统计信息如表 1 所示。其中：HS 是一个面对面接触的时间网络，是法国高中学生之间面对面接触的时间网络2；PS 是法国小学儿童与教师之间的时间网络2；Enron描述的是美国安然公司的电子邮件通信732023年 4月 15日Computer Engineering 计算机工程网络，每个时间边缘（u，v，t）表示用户 u 到 v 在时间 t时进行电子邮件通信；Dblp是作者的临时协作网络，每个时间边（u，v，t）表示两位作者 u和 v在时间 t合作撰写了一篇论文；Wikitalk描述维基百科对话交流网络；Youtube 描 述 的 是 Youtube 在 线 社 交 网 络；Mathoverflow 描述的是数学评论，问题和答案之间的关系。3.3性能比较分析本文实验的评价指标包括：1）MPC算法与EMP算法运行时间；2）不同参数对EMP算法运行时间的影响；3）3个剪枝策略的剪枝效率；4）EMP不同算法在各数据集上的运行时间。3.3.1MPC与 EMP算法运行时间对比给定值 K=4 和=4，EMP 和 MPC 算法在 10 个不同的数据集上的运行时间对比如图 7 所示。从图 7 可以看出：1）2 个算法在 Lkml、Dblp、00chess、Youtube这 4 个数据集上的运行时间差距较小，接近1.2倍；2）在 PS、Askubuntu这 2个数据集的运行时间差 距 稍 微 大 一 点，接 近 6 倍；3）在 Mathoverflow、Wikitalk这 2个数据集上的运行时间差距较大，都在15 倍以上。主要原因是：1）在剪枝时，EMP 算法避免产生 MPC 算法的重复计算问题；2）在求解时，采用先枚举极大团的方法，EMP 算法避免了 MPC 算法在图转化操作时带来的重复计算和枚举图规模变大等问题。EMP 算法在稀疏图上运行时间远快于MPC算法。3.3.2不同参数对 EMP算法运行时间的影响由于数据集的数量级差距太大，因此选取 5个具有代表性的数据集进行实验结果对比。在给定参数=4，不同 K 下，EMP 算法在 Lkml、HS、PS、Enron 和Dblp 数据集上的运行时间对比如表 2 所示。在给定参数K=4与不同下，EMP算法在Lkml、HS、PS、Enron和Dblp数据集上的运行时间对比如表3所示。从表 2 和表 3 可以看出：无论是参数 K 一定，参数 越大，还是参数 一定，参数 K 越大，EMP 算法运行时间越短。其原因为当参数 K 或者参数 逐渐增大时，顶点和边的约束随之逐渐加强，因此，经剪枝预处理后的图逐渐变小，求解算法的运行效率逐渐提高。由上述分析得到的结果可以通过时间复杂度 O（|V|+|E|+|T|21）辅助说明。表 1数据集信息统计 Table 1Inf