A local dense decision-making method for solving the maximum clique problem in large-scale undirected graphs

作     者：Yu, Zhuo Wang, Xiaofeng Zhao, Jian 

作者机构：North MinZu Univ Sch Comp Sci & Engn Yinchuan 750021 Peoples R China North MinZu Univ Key Lab Image Graph Intelligent Proc State Ethn Af Yinchuan 750021 Peoples R China Northwest Univ Sch Informat Sci & Technol Xian 710127 Peoples R China 

出 版 物：《COMPUTERS & ELECTRICAL ENGINEERING》 (计算机与电工)

年 卷 期：2022年第102卷

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Natural Science Foundation of China Northern University for Nationalities [ZDZX201901] Natural Science Foundation of Ningxia [2020AAC03214, 2020AAC03219] 

主　　题：The maximum clique Decision function Combination optimization Locally dense Branch and Bound 

摘      要：The maximum clique problem is a classic difficult problem. Most traditional solutions are branch and bound-based exact algorithms that perform well in terms of both accuracy and time at small legend sizes. However, in recent years, the scale of legend models in practical applications has expanded rapidly, and the traditional undirected graphical model solving methods are no longer applicable. At larger scales, a heuristic decision-making method for local density is proposed, a density index function is constructed, and a decision-making inference for finding maximum cliques is established. Our algorithm avoids random and disorderly traversal solutions, and it ensures the accuracy of the solution process. At the same time, a fast search threshold is added to the algorithm to improve the solution efficiency and local optimization ability. The experimental comparison shows that this algorithm and its improvements have better solution accuracy and solution time compared with the maximum clique accuracy algorithm.