大规模图例的最大团问题算法分析

doi:10.19678/j.issn.1000-3428.0063092

摘要/Abstract

摘要： 最大团问题是一个经典的组合优化问题，在蛋白质功能推测、竞胜标确定、视频对象分割等领域有广泛的应用。随着图例规模的增大，最大团问题求解难度增加，常规图例最大团求解算法已逐渐被大规模图例最大团求解算法取代。介绍求解大规模图例最大团问题的技术支撑点，重点总结基于大规模图例的最大团问题算法，并在大数据计算背景下对融合单层图划分方法和多层图划分方法的MapReduce框架和Spark框架进行优缺点分析。此外，比较k-core方法与k-community方法的应用场景，从算法分类的角度总结不同类型算法的优缺点，对求解大规模图例最大团问题的确定型算法进行梳理，并对代表性的求解算法在公开数据集中的表现进行对比分析。基于分析结果，指出不同算法在求解大规模图例最大团问题时需要重点关注的方面，并展望了智能优化算法、分层式深度强化学习方法、图结构相变分析技术的未来研究方向。

关键词: 最大团问题, 大规模图例, 图划分, 确定型算法, core结构

Abstract: The Maximal Clique Problem (MCP) is a classical combinatorial optimization problem that is widely appraised in protein function prediction, competitive bid determination, and video object segmentation. With an increase in graph size, the difficulty of solving the MCP increases, and the requirement for solving timeliness also increases.The conventional maximum clique-solving algorithm has been gradually replaced by the large-scale maximum clique-solving algorithm.This paper reviews the conventional algorithms for solving the MCP, focuses on the algorithm for solving the MCP based on large-scale graphs, and analyzes the advantages and disadvantages of the MapReduce and Spark frameworks by combining single-and multi-layer graph partitioning methods under the background of big data computing.The application scenarios of k-core method and k-community method are compared, and the advantages and disadvantages of different types of algorithms are presented from the perspective of algorithm classification.In particular, the validation algorithms for solving large-scale MCP are sorted, and the performances of representative algorithms in public datasets are compared and analyzed.Based on the abovementioned analysis results, we point out the aspects that need to be considered when different algorithms are used to solve the MCP of large-scale graphs, and focus on the future directions of intelligent optimization algorithms, layered deep reinforcement learning methods, and graph structure phase change analysis.

Key words: Maximum Clique Problem(MCP), large-scale graph, graph partition, exact algorithm, core structure

中图分类号:

TP391

王晓峰, 于卓, 赵健, 曹泽轩. 大规模图例的最大团问题算法分析[J]. 计算机工程, 2022, 48(6): 182-192,199.

WANG Xiaofeng, YU Zhuo, ZHAO Jian, CAO Zexuan. Algorithm Analysis for Solving Maximum Clique Problems of Large-scale Graphs[J]. Computer Engineering, 2022, 48(6): 182-192,199.

https://www.ecice06.com/CN/Y2022/V48/I6/182

图/表 14

20220625175618

20220625175622

20220625175626

20220625175630

20220625175634

20220625175638

20220625175642

20220625175645

20220625175650

20220625175655

20220625175658

20220625175703

20220625175707

20220625175711

参考文献

[1] 黄包裕, 张永祥, 赵磊.基于布谷鸟搜索算法和最大二阶循环平稳盲解卷积的滚动轴承故障诊断方法[J].机械工程学报, 2021, 57(9):99-107. HUANG B Y, ZHANG Y X, ZHAO L.Research on fault diagnosis method based on cuckoo search algorithm and maximum second-order cyclostationary blind deconvolution[J].Chinese Journal of Mechanical Engineering, 2021, 57(9):99-107.(in Chinese)
[2] MENG X, XIANG J, ZHENG R, et al.DPCMNE:detecting protein complexes from protein-protein interaction networks via multi-level network embedding[J].IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2021, 99:12-19.
[3] YANG S, ZHANG L, QI J Q, et al.Learning motion-appearance co-attention for zero-shot video object segmentation[C]//Proceedings of IEEE/CVF International Conference on Computer Vision.Washington D.C., USA:IEEE Press, 2021:1544-1553.
[4] GSCHWIND T, IRNICH S, FURINI F, et al.A branch-and-price framework for decomposing graphs into relaxed cliques[J].Informs Journal on Computing, 2021, 33(3):1070-1090.
[5] ZHANG M X, LI L, HUA W, et al.Efficient 2-hop labeling maintenance in dynamic small-world networks[C]//Proceedings of the 37th International Conference on Data Engineering.Washington D.C., USA:IEEE Press, 2021:133-144.
[6] VASCONCELOS G L, MACÊDO A M S, DUARTE-FILHO G C, et al.Power law behaviour in the saturation regime of fatality curves of the COVID-19 pandemic[J].Scientific Reports, 2021, 11(1):1-12.
[7] ZHONG H N, MAHDAVI PAJOUH F, PROKOPYEV O A.Finding influential groups in networked systems:the most degree-central clique problem[J].Omega, 2021, 101:102262-102271.
[8] SHI J, DHULIPALA L, SHUN J L.Parallel clique counting and peeling algorithms[C]//Proceedings of SIAM Conference on Applied and Computational Discrete Algorithms.Philadelphia, USA:Society for Industrial and Applied Mathematics, 2021:135-146.
[9] BESTA M, KANAKAGIRI R, KWASNIEWSKI G, et al.SISA:set-centric instruction set architecture for graph mining on processing-in-memory systems[C]//Proceedings of the 54th Annual IEEE/ACM Conference on International Symposium on Microarchitecture.Washington D.C., USA:IEEE Press, 2021:282-297.
[10] JIN Y, XIONG B W, HE K, et al.On fast enumeration of maximal cliques in large graphs[J].Expert Systems With Applications, 2022, 187:115915-115923.
[11] PARDALOS P M, XUE J.The maximum clique problem[J].Journal of Global Optimization, 1994, 4(3):301-328.
[12] PLACHETTA R, VAN DER GRINTEN A.SAT-and-reduce for vertex cover:accelerating branch-and-reduce by SAT solving[C]//Proceedings of Workshop on Algorithm Engineering and Experiments.Philadelphia, USA:Society for Industrial and Applied Mathematics, 2021:169-180.
[13] HOSSEINIAN S, FONTES D B M M, BUTENKO S.A Lagrangian bound on the clique number and an exact algorithm for the maximum edge weight clique problem[J].Informs Journal on Computing, 2020, 32(3):747-762.
[14] BABKIN E, BABKINA T, DEMIDOVSKIJ A.Hybrid neural network and bi-criteria tabu-machine:comparison of new approaches to maximum clique problem[J].International Journal of Big Data Intelligence, 2018, 5(3):143-149.
[15] JI P, ZHANG S X, ZHOU Z P.Overlapping community detection based on maximal clique and multi-objective ant colony optimization[C]//Proceedings of Chinese Control and Decision Conference. Washington D.C., USA:IEEE Press, 2020:5164-5169.
[16] 杜鹏.一种启发式的分布式最大独立集算法[J].南京邮电大学学报(自然科学版), 2013, 33(6):18-23, 28. DU P.A heuristic distributed algorithm for the maximum weight independent set problem[J].Journal of Nanjing University of Posts and Telecommunications (Natural Science), 2013, 33(6):18-23, 28.(in Chinese)
[17] WU Q H, HAO J K.A review on algorithms for maximum clique problems[J].European Journal of Operational Research, 2015, 242(3):693-709.
[18] SINGH K K, PANDEY A K.Survey of algorithms on maximum clique problem[J].International Advanced Research Journal in Science, Engineering and Technology, 2015, 2(2):18-20.
[19] FAKHFAKH F, TOUNSI M, MOSBAH M, et al.Algorithms for finding maximal and maximum cliques:a survey[C]//Proceedings of International Conference on Intelligent Systems Design and Applications.Berlin, Germany:Springer, 2017:745-754.
[20] NASIRIAN F, MAHDAVI PAJOUH F, BALASUNDARAM B.Detecting a most closeness-central clique in complex networks[J].European Journal of Operational Research, 2020, 283(2):461-475.
[21] LIU Y, LI C M, JIANG H, et al.A learning based branch and bound for maximum common subgraph related problems[C]//Proceedings of AAAI Conference on Artificial Intelligence.San Francisco, USA:AAAI Press, 2020, 34(3):2392-2399.
[22] MOHAMMADI N, KADIVAR M.NK-MaxClique and MMCQ:tow new exact branch and bound algorithms for the maximum clique problem[J].IEEE Access, 2020, 8:180045-180053.
[23] JIANG H, LI C M, LIU Y, et al.A two-stage maxsat reasoning approach for the maximum weight clique problem[C]//Proceedings of AAAI Conference on Artificial Intelligence.San Francisco, USA:AAAI Press, 2018:159-165.
[24] MALEKI N, RAHMANI A M, CONTI M.MapReduce:an infrastructure review and research insights[J].The Journal of Supercomputing, 2019, 75(10):6934-7002.
[25] XIANG J G, GUO C, ABOULNAGA A.Scalable maximum clique computation using MapReduce[C]//Proceedings of the 29th International Conference on Data Engineering.Washington D.C., USA:IEEE Press, 2013:74-85.
[26] 顾军华, 霍士杰, 武君艳, 等.求解最大团问题的并行多层图划分方法[J].计算机应用, 2018, 38(12):3425-3432. GU J H, HUO S J, WU J Y, et al.Parallel multi-layer graph partitioning method for solving maximum clique problems[J].Journal of Computer Applications, 2018, 38(12):3425-3432.(in Chinese)
[27] 肖成龙, 聂紫阳, 王宁, 等.基于并行约束规划的最大团识别研究[J].计算机工程, 2020, 46(4):53-59, 69. XIAO C L, NIE Z Y, WANG N, et al.Research on maximum clique identification based on parallel constraint programming[J].Computer Engineering, 2020, 46(4):53-59, 69.(in Chinese)
[28] HASHEM I A T, ANUAR N B, MARJANI M, et al.MapReduce scheduling algorithms:a review[J].The Journal of Supercomputing, 2020, 76(7):4915-4945.
[29] GUO J J, ZHANG S Q, GAO X, et al.Parallel graph partitioning framework for solving the maximum clique problem using Hadoop[C]//Proceedings of the 2nd International Conference on Big Data Analysis.Washington D.C., USA:IEEE Press, 2017:186-192.
[30] ARFAT Y, SUMA S, MEHMOOD R, et al.Parallel shortest path big data graph computations of US road network using apache spark:survey, architecture, and evaluation[C]//Proceedings of Conference on Smart Infrastructure and Applications.Berlin, Germany:Springer, 2020:185-214.
[31] MUKHERJEE A P, TIRTHAPURA S.Enumerating maximal bicliques from a large graph using MapReduce[J].IEEE Transactions on Services Computing, 2017, 10(5):771-784.
[32] WATTS D J, STROGATZ S H.Collective dynamics of small-world networks[J].Nature, 1998, 393:440-442.
[33] KABIR H, MADDURI K.Parallel k-core decomposition on multicore platforms[C]//Proceedings of IEEE International Parallel and Distributed Processing Symposium Workshops.Washington D.C., USA:IEEE Press, 2017:1482-1491.
[34] ROSSI R A, GLEICH D F, GEBREMEDHIN A H.Parallel maximum clique algorithms with applications to network analysis[J].SIAM Journal on Scientific Computing, 2015, 37(5):589-616.
[35] PELOFSKE E, HAHN G, DJIDJEV H.Solving large maximum clique problems on a quantum annealer[C]//Proceedings of International Conference on Quantum Technology and Optimization Problems.Berlin, Germany:Springer, 2019:123-135.
[36] YU Y, LEI Z Y, WANG Y R, et al.Improving dendritic neuron model with dynamic scale-free network-based differential evolution[J].IEEE/CAA Journal of Automatica Sinica, 2022, 9(1):99-110.
[37] JURSA A.Fast algorithm for finding maximum clique in scale-free networks[EB/OL].[2021-09-12].https://www.semanticscholar.org/paper/Fast-Algorithm-for-Finding-Maximum-Clique-in-Jursa/798fad2595830dfcae3d6c04075eb63c2977818b.
[38] VERMA A, BUCHANAN A, BUTENKO S.Solving the maximum clique and vertex coloring problems on very large sparse networks[J].Informs Journal on Computing, 2015, 27(1):164-177.
[39] SAN SEGUNDO P, ARTIEDA J, BATSYN M, et al.An enhanced bitstring encoding for exact maximum clique search in sparse graphs[J].Optimization Methods and Software, 2017, 32(2):312-335.
[40] BATAGELJ V, ZAVERSNIK M.An O (m) algorithm for cores decomposition of networks[EB/OL].[2021-09-12].https://arxiv.org/abs/cs/0310049.
[41] JIANG H, LI C M, MANYÀ F.Combining efficient preprocessing and incremental MaxSAT reasoning for MaxClique in large graphs[C]//Proceedings of the 22nd European Conference on Artificial Intelligence.[S.l.]:IOS Press 2016:939-947.
[42] LI C M, JIANG H, XU R C.Incremental MaxSAT reasoning to reduce branches in a branch-and-bound algorithm for MaxClique[C]//Proceedings of International Conference on Learning and Intelligent Optimization.Berlin, Germany:Springer, 2015:268-274.
[43] SVENDSEN M, MUKHERJEE A P, TIRTHAPURA S.Mining maximal cliques from a large graph using MapReduce:tackling highly uneven subproblem sizes[J].Journal of Parallel and Distributed Computing, 2015, 79:104-114.
[44] LI C M, JIANG H, MANYÀ F.On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem[J].Computers & Operations Research, 2017, 84:1-15.
[45] SAN SEGUNDO P, LOPEZ A, PARDALOS P M.A new exact maximum clique algorithm for large and massive sparse graphs[J].Computers & Operations Research, 2016, 66:81-94.
[46] WALTEROS J L, BUCHANAN A.Why is maximum clique often easy in practice?[J].Operations Research, 2020, 68(6):1866-1895.
[47] EMAMZADEH ESMAEILI NEJAD A, ZOLGHADRI JAHROMI M, TAHERI M.Graph compression based on transitivity for neighborhood query[J].Information Sciences, 2021, 576:312-328.
[48] YOLCU E, PÓCZOS B.Learning local search heuristics for boolean satisfiability[EB/OL].[2021-09-12].https://www.doc88.com/p-25629059165440.html?r=1.
[49] LI Z W, CHEN Q F, KOLTUN V.Combinatorial optimization with graph convolutional networks and guided tree search[EB/OL].[2021-09-12].https://www.semanticscholar.org/paper/Combinatorial-Optimization-with-Graph-Convolu tional-Li-Chen/d77c0e84972c256a8922b952b04330e369f65f09.
[50] MANCHANDA S, MITTAL A, DHAWAN A, et al.Learning heuristics over large graphs via deep reinforcement learning[EB/OL].[2021-09-12].https://arxiv.org/abs/1903.03332.
[51] 李凯文, 张涛, 王锐, 等.基于深度强化学习的组合优化研究进展[J].自动化学报, 2021, 47(11):2521-2537. LI K W, ZHANG T, WANG R, et al.Research reviews of combinatorial optimization methods based on deep reinforcement learning[J].Acta Automatica Sinica, 2021, 47(11):2521-2537.(in Chinese)
[52] BACCIU D, CONTE A, GROSSI R, et al.K-plex cover pooling for graph neural networks[J].Data Mining and Knowledge Discovery, 2021, 35(5):2200-2220.
[53] SUN Y, ERNST A, LI X D, et al.Generalization of machine learning for problem reduction:a case study on travelling salesman problems[J].OR Spectrum, 2021, 43(3):607-633.
[54] 王潮, 姚皓南, 王宝楠, 等.量子计算密码攻击进展[J].计算机学报, 2020, 43(9):1691-1707. WANG C, YAO H N, WANG B N, et al.Progress in quantum computing cryptography attacks[J].Chinese Journal of Computers, 2020, 43(9):1691-1707.(in Chinese)
[55] ARGELICH J, LI C M, MANYÀ F, et al.Clause tableaux for maximum and minimum satisfiability[J].Logic Journal of the IGPL, 2019, 29(1):7-27.
[56] GURSKI F, KOMANDER D, REHS C.How to compute digraph width measures on directed co-graphs[J].Theoretical Computer Science, 2021, 855:161-185.
[57] GEORGE R, SHUJAEE K, KERWAT M, et al.A comparative evaluation of community detection algorithms in social networks[J].Procedia Computer Science, 2020, 171:1157-1165.

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

选择包含的内容