计算机工程

作者：王晓峰, 于卓, 赵健, 曹泽轩

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

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

基金：国家自然科学基金（62062001）；北方民族大学重大专项（ZDZX201901）；宁夏自然科学基金（2020AAC03214，2020AAC03219）。

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

来源：2022年第6期

《计算机工程》期刊编辑部

查看计算机工程杂志2022年第6期