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

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.