An opposition-based memetic algorithm for the maximum quasi-clique problem

• DOI: 10.1016/j.ejor.2020.03.019
• Publication Date: 2020-03-21T00:31:57Z
• Authors: Qing Zhou; Una Benlic; Qinghua Wu
• Keywords: 0202 electrical engineering, electronic engineering, information engineering; 02 engineering and technology

Abstract Given a simple undirected graph G = ( V , E ) and a constant γ, the γ-quasi-clique is defined as a subset of vertices that induces a subgraph with the edge density of at least γ. The maximum γ-quasi-clique problem (MQCP) is to find a γ-quasi-clique of the maximum cardinality in G. This problem has many practical applications, especially in social network analysis. We present an opposition-based memetic algorithm (OBMA) for MQCP, which relies on a backbone-based crossover operator to generate new offspring solutions and on a constrained neighborhood tabu search for local improvement. OBMA further integrates the concept of opposition-based learning (OBL) to enhance the search ability of the classic memetic algorithm. Computational results on a large set of both dense and sparse graphs show that the proposed heuristic competes very favorably with the current state-of-the-art algorithms from the MQCP literature. In particular, it is able to find improved best-known solutions for 47 out of the 100 dense graphs, while reaching the best-known solution for all but few of the remaining instances. Several essential components of the proposed approach are investigated to understand their impacts to the algorithm’s performance.