A Fast Maximum k-Plex Algorithm Parameterized by the Degeneracy Gap
Authors: Zhengren Wang, Yi Zhou, Chunyu Luo, Mingyu Xiao
IJCAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We also carry out massive experiments and show that the algorithm is competitive with the state-of-the-art solvers. Additionally, for large k values such as 15 and 20, our algorithm has superior performance over existing algorithms. |
| Researcher Affiliation | Academia | Zhengren Wang , Yi Zhou , Chunyu Luo , Mingyu Xiao University of Electronic Science and Technology of China zr-wang@outlook.com, zhou.yi@uestc.edu.cn, Chunyu-Luo@std.uestc.edu.cn, myxiao@uestc.edu.cn |
| Pseudocode | Yes | Algorithm 1: Our framework for k-PLEX |
| Open Source Code | Yes | Codes and supplementary materials are enclosed at https: //github.com/joey001/kplex degen gap. |
| Open Datasets | Yes | We evaluate the algorithms with two sets of real-world graphs. Network-Repo Graphs. This dataset contains 139 realworld graphs with up to 5.87 107 vertices from the Network Data Repository 4, including social networks, biological networks, collaboration networks and so on. 10th-DIMACS Graphs. This dataset contains 84 graphs with up to 5.09 107 vertices 5, most of them are real-world graphs. These graphs have also been used in the literature [Gao et al., 2018; Zhou et al., 2021; Jiang et al., 2021; Chang et al., 2022]. 2nd-DIMACS Graphs This dataset contains 80 graphs with up to 4.00 103 vertices. Footnotes 1, 4, 5, 6 provide the URLs: http://dimacs.rutgers.edu/archive/Challenges/, http://lcs.ios.ac.cn/ caisw/Resource/realworld%20graphs.tar.gz, https://networkrepository.com/dimacs10.php, https://networkrepository.com/dimacs.php |
| Dataset Splits | No | The paper does not provide specific dataset split information (percentages, sample counts, or detailed methodology) for training, validation, or testing. |
| Hardware Specification | Yes | All experiments are conducted on a machine with an Intel(R) Xeon(R) Gold 6130 CPU @ 2.1GHz and a Ubuntu 22.04 operating system. Hyperthreading and turbo techniques are disabled for steady clock frequency. |
| Software Dependencies | Yes | Our algorithm is written in C++11 and compiled by G++ version 9.3.0 with -Ofast flag. |
| Experiment Setup | Yes | We carry out experiments with k = 2, 5, 10, 15, 20 and time limit 1800 seconds. |