SCCWalk: An efficient local search algorithm and its improvements for maximum weight clique problem

摘要

The maximum weight clique problem (MWCP) is an important generalization of the maximum clique problem with wide applications. In this study, we develop two efficient local search algorithms for MWCP, namely SCCWalk and SCCWalk4L, where SCCWalk4L is improved from SCCWalk for large graphs. There are two main ideas in SCCWalk, including strong configuration checking (SCC) and walk perturbation. SCC is a new variant of a powerful strategy called configuration checking for local search. The walk perturbation procedure is used to lead the algorithm to leave the current area and come into a new area of feasible solution space. Moreover, to improve the performance on massive graphs, we apply a low-complexity heuristic called best from multiple selection to select the swapping vertex pair quickly and effectively, resulting in the SCCWalk4L algorithm. In addition, SCCWalk4L uses two recent reduction rules to decrease the scale of massive graphs.