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

Algorithm Analysis for Solving Maximum Clique Problems of Large-scale Graphs

作　　者：王晓峰[1,2] 于卓 赵健[3] 曹泽轩 WANG Xiaofeng;YU Zhuo;ZHAO Jian;CAO Zexuan(School of Computer Science and Engineering,North Minzu University,Yinchuan 750021,China;Key Laboratory of Image and Graphics Intelligent Processing of State Ethnic Affairs Commission,North Minzu University,Yinchuan 750021,China;School of Information Science and Technology,Northwest University,Xi’an 710127,China)

机构地区：[1]北方民族大学计算机科学与工程学院,银川750021 [2]北方民族大学图像图形智能处理国家民委重点实验室,银川750021 [3]西北大学信息科学与技术学院,西安710127

出　　处：《计算机工程》2022年第6期182-192,199,共12页Computer Engineering

基　　金：国家自然科学基金(62062001);北方民族大学重大专项(ZDZX201901);宁夏自然科学基金(2020AAC03214,2020AAC03219)。

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

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

分 类 号：TP391[自动化与计算机技术—计算机应用技术]