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

摘要：

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

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

所属期刊栏目：48

分类号：TP391(计算技术、计算机技术)

资助基金：国家自然科学基金;北方民族大学重大专项;宁夏自然科学基金项目;宁夏自然科学基金项目

在线出版日期：2022-06-21（万方平台首次上网日期，不代表论文的发表时间）

页数：共12页

页码：182-192,199