图数据中极大团枚举问题的求解:研究现状与挑战  

Maximal clique enumeration problem on graphs:status and challenges

作　　者：许绍显 廖小飞[1,2,3,4] 邵志远 华强胜[1,2,3,4] 金海 Shaoxian XU;Xiaofei LIAO;Zhiyuan SHAO;Qiangsheng HUA;Hai JIN(School of Computer Science and Technology,Huazhong University of Science and Technology,Wuhan 430074,China;National Engineering Research Center for Big Data Technology and System,Wuhan 430074,China;Key Laboratory of Services Computing Technology and System,Ministry of Education,Wuhan 430074,China;Key Laboratory of Cluster and Grid Computing,Hubei Province,Wuhan 430074,China)

机构地区：[1]华中科技大学计算机科学与技术学院,武汉430074 [2]大数据技术与系统国家地方联合工程研究中心,武汉430074 [3]服务计算技术与系统教育部重点实验室,武汉430074 [4]集群与网格计算湖北省重点实验室,武汉430074

出　　处：《中国科学：信息科学》2022年第5期784-803,共20页Scientia Sinica(Informationis)

基　　金：国家自然科学基金(批准号:61972444,61832006,61825202,61702202)资助项目。

摘　　要：随着大数据时代的到来,图数据挖掘成为了一个热门的研究方向.极大团枚举(maximal clique enumeration,MCE)作为图论中的一个基本问题,在很多领域都有着广泛的应用.然而,鉴于极大团枚举问题本身的复杂性以及现实图数据规模的飞速增长,在现实图数据上进行极大团枚举是很耗时的.目前已经有大量的工作对该问题的求解算法进行改进,或采用各种计算优化方法减少算法的运行时间.本文就极大团枚举问题做了如下工作:对现有的极大团枚举问题的研究工作进行了分类归纳;对极大团枚举问题的研究现状进行了详细介绍;对该问题进一步发展所面临的挑战和发展方向进行了讨论和展望.In the era of big data,graph mining has become a popular research topic.The maximal clique enumeration(MCE),as a basic problem in graph theory,has been widely used in different fields.However,considering the complexity of the MCE problem and the rapid growth in the scale of real-world graphs,enumerating the maximal cliques in real-world graphs is time-consuming.A large number of researches have been performed to improve the algorithm for the MCE problem and to reduce the execution time by applying various computational optimizations.For the MCE problem,this survey has conducted the following works:existing research works on the MCE problem are classified,the research status of the MCE problem is introduced in detail,and the challenges and future directions of the MCE problem are discussed.

关 键 词：极大团枚举 图论 图数据挖掘 图划分 并行计算 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论] O157.5[自动化与计算机技术—计算机科学与技术]