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

doi:10.19678/j.issn.1000-3428.0064192

摘要/Abstract

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

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

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 length

中图分类号:

TP391

杜明, 郝燕, 周军锋, 谭玉婷. 一种高效的周期团挖掘方法[J]. 计算机工程, 2023, 49(4): 68-76.

DU Ming, HAO Yan, ZHOU Junfeng, TAN Yuting. An Efficient Method for Mining Periodic Cliques[J]. Computer Engineering, 2023, 49(4): 68-76.

http://www.ecice06.com/CN/Y2023/V49/I4/68

图/表 14

20230415183247

20230415183250

20230415183253

20230415183256

20230415183300

20230415183318

20230415183321

20230415183325

20230415183329

20230415183332

20230415183335

20230415183339

20230415183343

20230415183346

参考文献

[1] YANG Y, YAN D, WU H H, et al.Diversified temporal subgraph pattern mining[C]//Proceedings of the 22nd International Conference on Knowledge Discovery and Data Mining.New York, USA:ACM Press, 2016:1965-1974.
[2] REDMOND U, CUNNINGHAM P.Subgraph isomorphism in temporal networks[EB/OL].[2022-03-10].https://arxiv.org/pdf/1605.02174.pdf.
[3] MA S, HU R J, WANG L S, et al.Fast computation of dense temporal subgraphs[C]//Proceedings of the 33rd International Conference on Data Engineering.Washington D.C., USA:IEEE Press, 2017:361-372.
[4] VANHEMS P, BARRAT A, CATTUTO C, et al.Estimating potential infection transmission routes in hospital wards using wearable proximity sensors[J].PLoS One, 2013, 8(9):73970.
[5] FOURNET J, BARRAT A.Contact patterns among high school students[J].PLoS One, 2014, 9(9):107878.
[6] STEHLÉ J, VOIRIN N, BARRAT A, et al.High-resolution measurements of face-to-face contact patterns in a primary school[EB/OL].[2022-03-10].https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.405.2930&rep=rep1& type=pdf.
[7] QIN H C, LI R H, WANG G R, et al.Mining periodic cliques in temporal networks[C]//Proceedings of the 35th International Conference on Data Engineering.Washington D.C., USA:IEEE Press, 2019:1130-1141.
[8] BRON C, KERBOSCH J.Algorithm 457:finding all cliques of an undirected graph[J].Communications of the ACM, 1973, 16(9):575-577.
[9] WOOD D R.On the maximum number of cliques in a graph[J].Graphs and Combinatorics, 2007, 23(3):337-352.
[10] NIKOLETSEAS S, RAPTOPOULOS C, SPIRAKIS P G.Maximum cliques in graphs with small intersection number and random intersection graphs[C]//Proceedings of the 37th International Conference on Mathematical Foundations of Computer Science.New York, USA:ACM Press, 2012:728-739.
[11] MARCONI J, FOSTER J A.A hard problem for genetic algorithms:finding cliques in Keller graphs[C]//Proceedings of International Conference on Evolutionary Computation.Washington D.C., USA:IEEE Press, 2002:650-655.
[12] WANG J Y, ZENG Z P, ZHOU L Z.CLAN:an algorithm for mining closed cliques from large dense graph databases[C]//Proceedings of the 22nd International Conference on Data Engineering.Washington D.C., USA:IEEE Press, 2006:73.
[13] SUN H L, LU Z, LIU J L, et al.Top-k attribute difference q-clique queries in graph data[J].Chinese Journal of Computers, 2012, 35(11):2265.
[14] GAVRIL F.Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph[J].SIAM Journal on Computing, 1972, 1(2):180-187.
[15] BERRY A, POGORELCNIK R.A simple algorithm to generate the minimal separators and the maximal cliques of a chordal graph[J].Information Processing Letters, 2011, 111(11):508-511.
[16] LEHMANN K A, KAUFMANN M, STEIGELE S, et al.On the maximal cliques in c-max-tolerance graphs and their application in clustering molecular sequences[J].Algorithms for Molecular Biology, 2006, 1(1):1-17.
[17] SUN S L, WANG Y M, LIAO W L, et al.Mining maximal cliques on dynamic graphs efficiently by local strategies[C]//Proceedings of the 33rd International Conference on Data Engineering.Washington D.C., USA:IEEE Press, 2017:115-118.
[18] MACÊDO FILHO H B, MACHADO R C S, FIGUEIREDO C M H.Hierarchical complexity of 2-clique-colouring weakly chordal graphs and perfect graphs having cliques of size at least 3[C]//Proceedings of Latin American Symposium on Theoretical Informatics.Berlin, Germany:Springer, 2014:13-23.
[19] TOMITA E, TANAKA A, TAKAHASHI H.The worst-case time complexity for generating all maximal cliques and computational experiments[J].Theoretical Computer Science, 2006, 363(1):28-42.
[20] YANG Y J, YU J X, GAO H, et al.Mining most frequently changing component in evolving graphs[J].World Wide Web, 2014, 17(3):351-376.
[21] YUAN L, QIN L, LIN X M, et al.Diversified top-k clique search[J].The VLDB Journal, 2016, 25(2):171-196.
[22] SANEI-MEHRI S V, DAS A, TIRTHAPURA S.Enumerating top-k quasi-cliques[C]//Proceedings of International Conference on Big Data.Washington D.C., USA:IEEE Press, 2019:1107-1112.
[23] MUKHERJEE A P, XU P, TIRTHAPURA S.Mining maximal cliques from an uncertain graph[C]//Proceedings of the 31st International Conference on Data Engineering.Washington D.C., USA:IEEE Press, 2015:243-254.
[24] ZOU Z N, LI J Z, GAO H, et al.Finding top-k maximal cliques in an uncertain graph[C]//Proceedings of the 26th International Conference on Data Engineering.Washington D.C., USA:IEEE Press, 2010:649-652.
[25] CHENG J, KE Y P, FU A W C, et al.Finding maximal cliques in massive networks[J].ACM Transactions on Database Systems, 2011, 36(4):1-34.
[26] ROSSETTI G, CAZABET R.Community discovery in dynamic networks[J].ACM Computing Surveys, 2019, 51(2):1-37.
[27] 张天明, 徐一恒, 蔡鑫伟, 等.时态图最短路径查询方法[J].计算机研究与发展, 2022, 59(2):362-375. ZHANG T M, XU Y H, CAI X W, et al.A shortest path query method over temporal graphs[J].Journal of Computer Research and Development, 2022, 59(2):362-375.(in Chinese)
[28] 陈东明, 袁泽枝, 黄新宇, 等.时态网络节点相似性度量及链路预测算法[J].东北大学学报(自然科学版), 2020, 41(1):29-34, 43. CHEN D M, YUAN Z Z, HUANG X Y, et al.Node similarity measurement and link prediction algorithm in temporal networks[J].Journal of Northeastern University (Natural Science), 2020, 41(1):29-34, 43.(in Chinese)
[29] 程开原, 姚俊萍, 李晓军, 等.时态网络中知识图谱推荐:关键技术与研究进展[J].中国电子科学研究院学报, 2021, 16(2):174-183, 188. CHENG K Y, YAO J P, LI X J, et al.Recommendation based on knowledge graph in temporal networks:key technologies and progress[J].Journal of China Academy of Electronics and Information Technology, 2021, 16(2):174-183, 188.(in Chinese)
[30] HIMMEL A S, MOLTER H, NIEDERMEIER R, et al.Adapting the Bron-Kerbosch algorithm for enumerating maximal cliques in temporal graphs[J].Social Network Analysis and Mining, 2017, 7(1):1-16.

选择文件类型/文献管理软件名称

选择包含的内容