Nukplex: An Efficient Local Search Algorithm for Maximum K-Plex Problem
Authors: Rui Sun, Yiyuan Wang, Shimao Wang, Hui Li, Ximing Li, Minghao Yin
IJCAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | The experimental results show that the proposed algorithm significantly outperforms the state-of-the-art MKPP algorithms in almost all the instances. |
| Researcher Affiliation | Academia | Rui Sun1 , Yiyuan Wang1,2 , Shimao Wang1 , Hui Li1 , Ximing Li3,4 , Minghao Yin1,2, 1School of Computer Science and Information Technology, Northeast Normal University, China 2Key Laboratory of Applied Statistics of MOE, Northeast Normal University, Changchun, China 3College of Computer Science and Technology, Jilin University, China 4Key Laboratory of Symbolic Computation and Knowledge Engineering of MOE, Jilin University, China |
| Pseudocode | Yes | Algorithm 1: Core Perturb, Algorithm 2: Nukplex |
| Open Source Code | Yes | Source code and supplementary materials are available at https://github.com/yiyuanwang1988/Nukplex |
| Open Datasets | Yes | Our computational assessment was conducted on classic instances and sparse large instances for k = 2, 3, 4, 5, which were also reported in the previous MKPP studies [Zhou and Hao, 2017; Chen et al., 2020; Pullan, 2021; Jin et al., 2022]. First, we considered two classical benchmarks, including 80 and 41 graphs from DIMACS [Johnson and Trick, 1996] and BHOSLIB [Xu et al., 2007], respectively. We also evaluated Nukplex on sparse large instances, including 67 graphs from the Stanford Large Network Dataset Collection (SNAP)2 and the 10th DIMACS implementation challenge (DIMACS10)3 and 42 graphs from the Network Data Repository (NDR) [Rossi and Ahmed, 2015]. |
| Dataset Splits | Yes | According to our preliminary experiments by using the automatic configuration tool irace [L opez-Ib a nez et al., 2016]... we built a training set and randomly selected 10 instances from the corresponding tested benchmark. |
| Hardware Specification | Yes | All experiments are run on Intel Xeon Gold 6238 CPU @ 2.10GHz CPU with 512GB RAM under Cent OS 7.9. |
| Software Dependencies | No | The paper states 'All algorithms were implemented in C++ and compiled by g++ with -O3 option' and mentions 'the automatic configuration tool irace [L opez-Ib a nez et al., 2016]', but does not provide specific version numbers for the compiler or any other software dependencies. |
| Experiment Setup | Yes | Table 1 shows the selected parameter values: L=4000, t=50, Lt=4, ub thre=3, ρ=0.2, p=0.5. The cutoff time for classic instances is set to 1000 seconds, and for sparse large instances, it is 100 and 1000 seconds. |