NuQClq: An Effective Local Search Algorithm for Maximum Quasi-Clique Problem
Authors: Jiejiang Chen, Shaowei Cai, Shiwei Pan, Yiyuan Wang, Qingwei Lin, Mengyu Zhao, Minghao Yin12258-12266
AAAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experiments on a broad range of classic benchmarks and sparse instances show that Nu QClq significantly outperforms the state-of-the-art MQCP algorithms for most instances. |
| Researcher Affiliation | Collaboration | Jiejiang Chen1, Shaowei Cai2,4, Shiwei Pan1, Yiyuan Wang1,3*, Qingwei Lin5, Mengyu Zhao1, Minghao Yin1,3 1School of Computer Science and Information Technology, Northeast Normal University, China 2State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, China 3Key Laboratory of Applied Statistics of MOE, Northeast Normal University, Changchun, China 4School of Computer Science and Technology, University of Chinese Academy of Sciences, China 5Microsoft Research, China |
| Pseudocode | Yes | Algorithm 1: the Nu QClq Algorithm; Algorithm 2: QCSearch(S); Algorithm 3: Select Vertex To Add(S) |
| Open Source Code | Yes | Detailed results and our sourced code are reported in github5. 5https://github.com/yiyuanwang1988/NuQClq.git |
| Open Datasets | Yes | We evaluate Nu QClq on a broad range of classic benchmarks as well as sparse instances... 289 instances, which are mainly divided into two parts: (1) 187 classic instances from DIMACS benchmark (Johnson 1993)1 and BHOSLIB benchmark (Xu et al. 2007)2; (2) 102 sparse instances whose density is from 0.00014% to 3.869% from Florida Sparse Matrix Collection (Davis and Hu 2011)3 and Stanford Large Network Dataset Collection (Rossi and Ahmed 2015)4. |
| Dataset Splits | Yes | The automatic configuration tool irace (2016) is used to tune parameters for Nu QClq. For the training set, we collect 60 instances randomly chosen from all instances. |
| Hardware Specification | Yes | All experiments are run on Intel Xeon E5-2640 v4 @ 2.40GHz CPU with 128GB RAM under Cent OS 7.5. |
| Software Dependencies | No | Nu QClq, OBMA, and BRKGA-LSQClique are all implemented in C++ and complied by g++ with -O3 option, while TSQC is compiled by MATLAB. |
| Experiment Setup | Yes | For each instance, all algorithms are executed 10 times with random seeds from 1 to 10 and a cutoff time of 1000 seconds. The automatic configuration tool irace (2016) is used to tune parameters for Nu QClq. The final values obtained by irace are represented in Table 1. Parameters Ranges Final values: ub threshold 7, β 0.8, step Max 4000. |