A local dense decision-making method for solving the maximum clique problem in large-scale undirected graphs. (September 2022)

• Record Type: Journal Article
• Authors: Yu, Zhuo; Wang, Xiaofeng; Zhao, Jian
• Is Part Of: Computers & electrical engineering. Volume 102(2022)
• Publication Date: 2022-09
• Subjects: The maximum clique -- Decision function -- Combination optimization -- Locally dense -- Branch and Bound; Computer engineering -- Periodicals; Electrical engineering -- Periodicals; Electrical engineering -- Data processing -- Periodicals; Ordinateurs -- Conception et construction -- Périodiques; Électrotechnique -- Périodiques; Électrotechnique -- Informatique -- Périodiques; Computer engineering; Electrical engineering; Electrical engineering -- Data processing; Periodicals; Electronic journals; 621.302854
• DOI: 10.1016/j.compeleceng.2022.108220
• Languages: English
• ISSNs: 0045-7906

Abstract

Highlights: A good initial search sequence. Construct a new subplot to perform a contrastive search in the local legend. Iterative method to find the optimal solution. Multiple global pruning methods speed up the global optimal solution. Abstract: 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. Graphical abstract: Image, graphical abstract