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

Qing Zhou, Una Benlic and Qinghua Wu

European Journal of Operational Research, 2020, vol. 286, issue 1, 63-83

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.

Keywords: Heuristic; Quasi-clique; Opposition-based learning; Constrained neighborhood; Memetic algorithm (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221720302332
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:286:y:2020:i:1:p:63-83

DOI: 10.1016/j.ejor.2020.03.019

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().