A local search algorithm with hybrid strategies for the maximum weighted quasi-clique problem

Identifying cohesive subgraphs is an important topic in graph theory and complex network analysis. The quasi-clique, as a generalization of clique, can be used to identify functional and structural properties of various networks. In this paper, we study the maximum weighted quasi-clique problem, and propose a local search algorithm for solving the problem. In the algorithm, an iterated local search method is used as the search framework. To find the quasi-clique with the maximum total weights, hybrid vertex selection strategies are proposed and incorporated into our algorithm. The hybrid strategies utilize a probability-based mechanism for choosing sub-strategies in each round of the local search. We conduct experiments on synthetic networks and real-world networks to show the effectiveness of our algorithm. The results indicate that hybrid strategies perform better than existing methods, and thus our algorithm has a good ability to tackle various networks.