Liu Shuhong, Zhou Jincheng, Wang Dan, Zhang Zaijun, Lei Mingjie
State Key Laboratory of Public Big Data, College of Computer Science and Technology, Guizhou University, Guiyang, Guizhou, China.
Key Laboratory of Complex Systems and Intelligent Optimization of Guizhou Province, Duyun, Guizhou, China.
PeerJ Comput Sci. 2024 Jul 12;10:e2173. doi: 10.7717/peerj-cs.2173. eCollection 2024.
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.
图论中的最大团问题是一个著名的挑战，它涉及在给定图中识别节点数量最多的完全子图，这是一个非确定性多项式时间内难以解决的问题（NP难问题）。虽然很难找到最大团问题在现实世界中的确切应用，但松弛团模型准团已经出现，并广泛应用于生物信息学和社会网络分析等领域。本研究聚焦于最大准团问题，并介绍了两种算法，NF1和NR1。这些算法通过信息反馈模型利用先前的迭代信息，使用适应度加权计算信息反馈得分，并基于基准算法和选定的先前个体更新当前迭代中的个体。大量合成图和真实世界图的实验结果表明，这两种算法在密集实例中均优于原始基准算法，同时在稀疏实例中也取得了可比的结果。
