An optimization algorithm for maximum quasi-clique problem based on information feedback model

Abstract

The maximum clique problem in graph theory is a well-known challenge that involves identifying the complete subgraph with the highest number of nodes in a given graph, which is a problem that is hard for nondeterministic polynomial time (NP-hard problem). While finding the exact application of the maximum clique problem in the real world is difficult, the relaxed clique model quasi-clique has emerged and is widely applied in fields such as bioinformatics and social network analysis. This study focuses on the maximum quasi-clique problem and introduces two algorithms, NF1 and NR1. These algorithms make use of previous iteration information through an information feedback model, calculate the information feedback score using fitness weighting, and update individuals in the current iteration based on the benchmark algorithm and selected previous individuals. The experimental results from a significant number of composite and real-world graphs indicate that both algorithms outperform the original benchmark algorithm in dense instances, while also achieving comparable results in sparse instances.

Keywords

• γ-quasi-clique
• Metaheuristic algorithm
• Information feedback model
• Historical iteration