一种高效的周期团挖掘方法_杜明.pdf
《一种高效的周期团挖掘方法_杜明.pdf》由会员分享,可在线阅读,更多相关《一种高效的周期团挖掘方法_杜明.pdf(9页珍藏版)》请在咨信网上搜索。
1、第 49卷 第 4期2023年 4月Computer Engineering 计算机工程一种高效的周期团挖掘方法杜明,郝燕,周军锋,谭玉婷(东华大学 计算机科学与技术学院,上海 201620)摘要:周期团是在时态网络上出现时机满足特定周期要求的完全子图,周期团挖掘用于挖掘时态图中具有周期性的团。针对现有周期团挖掘方法效率低的问题,设计三种高效的剪枝策略 EMP-FlagVex、EMP-FlagEdge和 EMP-FlagEdge+,并提出一种基于边上时间戳序列的求解方法 EMP。枚举满足要求的极大团,并对枚举出的极大团进行周期验证。验证操作是提取极大团每条边上的时间戳集合,并对集合中出现的时间
2、点进行计数。若某个时间点出现的次数等于提取的集合个数,则将其放入新集合。在此基础上,判断新集合中的序列是否具有周期性。实验结果表明,相比基础方法 EMP,将 EMP与 EMP-FlagEdge+剪枝策略相结合的方法在 PS、Lkml、Enron等数据集上的运行时间加快了 15倍以上。相比 MPC 算法,基于顶点度数的 EMP-FlagVex剪枝策略的挖掘效率提高约 1倍,基于边上时间戳序列长度的 EMP-FlagEdge剪枝策略的挖掘效率提高 10倍,基于周期子序列长度的 EMP-FlagEdge+剪枝策略的挖掘效率提高约 30倍。关键词:时态网络;周期团;时间戳;剪枝策略;最长周期序列;周期
3、长度开放科学(资源服务)标志码(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 Com
4、puter 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
5、 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 v
6、erify 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 s
7、et.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.Compare
8、d 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 l
9、ength 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时刻有联系
10、。在电子邮件通信网络中,每封电子邮件都包含一个发送者和一个接收者,以及发送电子邮件的时间。在科学协作网络中,每条边(u,v,t)表示两个作者 u和 v在时间 t共同完成一篇论文。基金项目:国家自然科学基金(61472339,61873337);上海市自然科学基金(20ZR1402700)。作者简介:杜明(1975),男,副教授、博士,主研方向为自然语言处理、信息查询、数据分析;郝燕(通信作者),硕士研究生;周军锋,教授、博士、博士生导师、CCF会员;谭玉婷,博士。收稿日期:2022-03-16 修回日期:2022-05-19 Email:人工智能与模式识别文章编号:1000-3428(2023
11、)04-0068-09 文献标志码:A 中图分类号:TP391第 49卷 第 4期杜明,郝燕,周军锋,等:一种高效的周期团挖掘方法周期团7是时态网络上出现时机满足特定周期要求的完全子图,其任意两个顶点都有边连接。周期团挖掘对于理解和预测时态网络中的群体行为是非常重要的。例如,在 Dblp 科学写作网络中,A、B、C、D 这 4 位作者在某段时间共同合作撰写论文,可以将其建模为一个含有时间信息的时态网络。这4位作者在 20192021年进行相互协作,则组成的社区具有周期性,能够预测 4 位作者将在 2022 年再次合作。QIN 等7提出现有的周期团挖掘方法,设计剪枝+求解的 MPC(Mining
12、 Periodic Cliques)算法来求解周期团,但是该算法在剪枝和求解两个阶段都存在效率低、重复计算等问题。在剪枝阶段,MPC 算法需要多次遍历图中的顶点和边并判断其是否具有符合条件的周期序列,以删除不满足周期性要求的顶点和边。在求解阶段,MPC 算法使用图转换的方法求解周期团,图转化即从剪枝后的时态图中导出具有相同周期的子图,分别在不同子图上求解满足规模要求的团。在图转化阶段,该算法需要重新计算顶点的周期,增加了计算量。同一个时态图在图转换之后可能生成多个子图,使得枚举图规模增大,导致枚举效率降低。本文设计 3 种高效的剪枝策略 EMP-FlagVex、EMP-FlagEdge、EMP
13、-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-
14、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,
15、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和基于不确定图1
16、9-23的枚举算法24-26。本文是在确定图上进行挖掘,只介绍基于确定图的枚举算法。基于确定图的枚举算法主要是 BK算法。BK算法的基本形式是一种递归回溯算法。总体上,给定3个不相交的顶点集 R、P、X,该算法找到包含 R中的所有顶点,P 中的某些顶点和不在 X 中顶点的极大团。在 BK 算法的每次调用中,P 和 X 是不相交的集合,它们的并集由添加到 R 时形成团的那些顶点组成,即 PX 是连接到 R 每个元素的一组顶点。当 P和 X 都为空时,没有其他元素可以添加到 R,因此,R是极大团,算法输出 R。2)在时态网络上的挖掘方法现有关于时态网络上的挖掘算法比较少,对于时态网络的研究主要有张
17、天明等27提出的时态图最短路径查询方法、陈东明等28提出的时态网络节点相似性度量及链路预测算法以及程开原等29提出的时态网络中知识图谱推荐:关键技术与研究进展。关 于 时 态 网 络 上 周 期 团 的 研 究 主 要 有 HIMMEL等30提出将 BK算法应用在时态图上的极大团枚举,QIN等7提出的时态网络中周期团挖掘,主要用于挖掘时态网络中具有周期性的社区。文献 7 提出时态网络中周期团挖掘问题。剪枝过程示例如图 1所示。在图 1(a)所示的时态图上求解周期长度为 3,顶点规模为 4 的周期团。首先,遍历图中所有顶点并计算其周期,顶点 v8的周期为 1,2,不满足条件,被删除。然后,与 v
18、8相连接的顶点 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)所示的结果。针对该剪枝方
19、法存在的不足,本文提出新的剪枝策略。该剪枝策略只需要将不满足大小及周期阈值要求的顶点和边删除,其原因为本文所提的求解方法不需要在周期图上操作。同样地,对于图 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)所示的结果,该过程不存在重复计算的问题。
20、将图1(b)所示的周期图进行转化,先计算顶点的周期,再将具有相同周期的顶点相连接。图转化方法示意图如图2所示,图2(b)和图2(c)所示为2个子图的示意图。对图2(b)所示的时态子图,MPC算法需要在图2(b)和图2(c)所示的转换后顶点规模为6的时态图上进行枚举操作,而本文算法只需要在图2(b)所示的顶点规模为 4的时态图上进行操作。2EMP算法 2.1EMP算法思想该算法首先找到图中满足条件的极大团,然后判断该团是否为周期团,即判断每条边是否存在相同的周期序列。因此,本文从边上的时间戳集合着手,提取该极大团所有边上的时间戳集合和该集合中对应的时间并计数。若某个时间出现的次数与提取的时间戳集
21、合个数相等,说明每条边都会出现在这个时间,如果这些时间呈现周期规律,那么该团就是周期团。求解过程示例如图 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)-周期团。在验证阶段有一个特殊情况,即验证的极大团不是周期团,但其子团是周期团的情况,这种情况采
22、用枚举的方法进行再挖掘。枚举过程示例如图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,将用于在枚举所有周期团时进行剪枝。引理
23、 1 任何一个属于(,K)-周期团的顶点一定包含在 EMP-FlagVex剪枝后的时态图中。证明 假设存在一个顶点属于(,K)-周期团,但是不包含EMP-FlagVex剪枝后的时态图中,(,K)-周期团顶点的度为 K1,而不包含在 EMP-FlagVex剪枝后的时态图中顶点的度小于 K1,相互矛盾。定理1 给定一个时态图G,参数K,如果存在EMP-FlagVex剪枝后的时态图,那么时态图 G中必是唯一。证明 假设EMP-FlagVex剪枝后的时态图不唯一,即存在另一个时态图。在该时态图中具有EMP-FlagVex剪枝后的时态图不存在的顶点或者没有EMP-FlagVex剪枝后的时态图中存在的顶点
24、。在不存在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剪枝后的时态
25、图是时态图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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 一种 高效 周期 挖掘 方法 杜明
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。