An Efficient Local Search for the Maximum Clique Problem on Massive Graphs

The Maximum Clique Problem (MCP) is one of the most important combinatorial optimization problems that has many practical applications such as community search in social networks. Since the MCP is known to be NP-hard, much effort has been devoted to the development of metaheuristic algorithms to find a high quality clique (solution) within reasonable running times. The Multi-start k-opt Local Search incorporating k-opt local search (MKLS) is well known as a simple and effective metaheuristic for MCP. However it takes long time to search the high-quality solution for difficult massive graphs such as real world social networks, because the search space is too large. In the case of applying metaheuristic algorithms for massive sparse graphs, adequate process such as reduction process is necessary to focus on promising search space. In this paper, we present a Multi-start k-opt Local Search with graph Reduction process (MKLS-R), for solving the maximum clique problem on massive graphs. MKLS-R is evaluated on difficult massive graphs of Network-Repository graphs. The experimental results showed that the graph reduction process in MKLS-R contributes to the improvement of the search performance of MKLS for the difficult massive graphs.