NuQClq: An Effective Local Search Algorithm for Maximum Quasi-Clique Problem

Authors

  • Jiejiang Chen School of Computer Science and Information Technology, Northeast Normal University, China
  • Shaowei Cai State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, China School of Computer Science and Technology, University of Chinese Academy of Sciences, China
  • Shiwei Pan School of Computer Science and Information Technology, Northeast Normal University, China
  • Yiyuan Wang School of Computer Science and Information Technology, Northeast Normal University, China Key Laboratory of Applied Statistics of MOE, Northeast Normal University, Changchun, China
  • Qingwei Lin Microsoft Research, China
  • Mengyu Zhao School of Computer Science and Information Technology, Northeast Normal University, China
  • Minghao Yin School of Computer Science and Information Technology, Northeast Normal University, China Key Laboratory of Applied Statistics of MOE, Northeast Normal University, Changchun, China

Keywords:

Local Search, Heuristic Search

Abstract

The maximum quasi-clique problem (MQCP) is an important extension of maximum clique problem with wide applications. Recent heuristic MQCP algorithms can hardly solve large and hard graphs effectively. This paper develops an efficient local search algorithm named NuQClq for the MQCP, which has two main ideas. First, we propose a novel vertex selection strategy, which utilizes cumulative saturation information to be a selection criterion when the candidate vertices have equal values on the primary scoring function. Second, a variant of configuration checking named BoundedCC is designed by setting an upper bound for the threshold of forbidding strength. When the threshold value of vertex exceeds the upper bound, we reset its threshold value to increase the diversity of search process. Experiments on a broad range of classic benchmarks and sparse instances show that NuQClq significantly outperforms the state-of-the-art MQCP algorithms for most instances.

Downloads

Published

2021-05-18

How to Cite

Chen, J., Cai, S., Pan, S., Wang, Y., Lin, Q., Zhao, M., & Yin, M. (2021). NuQClq: An Effective Local Search Algorithm for Maximum Quasi-Clique Problem. Proceedings of the AAAI Conference on Artificial Intelligence, 35(14), 12258-12266. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/17455

Issue

Section

AAAI Technical Track on Search and Optimization