loading page

A local search algorithm with hybrid strategies for the maximum weighted quasi-clique problem
  • Jincheng Zhou,
  • Shuhong Liu,
  • Jian Gao
Jincheng Zhou
Qiannan Normal University for Nationalities

Corresponding Author:[email protected]

Author Profile
Shuhong Liu
Guizhou University
Author Profile
Jian Gao
Northeast Normal University
Author Profile


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.
07 Nov 2022Submitted to Electronics Letters
07 Nov 2022Assigned to Editor
07 Nov 2022Submission Checks Completed
09 Nov 2022Reviewer(s) Assigned
17 Nov 2022Review(s) Completed, Editorial Evaluation Pending
21 Nov 2022Editorial Decision: Accept
Jan 2023Published in Electronics Letters volume 59 issue 1. 10.1049/ell2.12685