A local search algorithm with hybrid strategies for the maximum weighted
quasi-clique problem
- Jincheng Zhou
, - Shuhong Liu,
- Jian Gao
Abstract
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 2022Submission Checks Completed
07 Nov 2022Assigned to Editor
09 Nov 2022Reviewer(s) Assigned
17 Nov 2022Review(s) Completed, Editorial Evaluation Pending
21 Nov 2022Editorial Decision: Accept