Enumerating Maximalk-Plexes with Worst-Case Time Guarantee
Authors: Yi Zhou, Jingwei Xu, Zhenyu Guo, Mingyu Xiao, Yan Jin2442-2449
AAAI 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We finally carry out experiments on both real and synthetic graphs and demonstrate that our algorithms run much faster than the state-of-the-art algorithms. |
| Researcher Affiliation | Academia | 1University of Electronic Science and Technology of China, 2Huazhong University of Science and Technology |
| Pseudocode | Yes | Algorithm 1: The recursion scheme of conventional kplex enumeration |
| Open Source Code | Yes | All the codes and data are publicly available at https:// github.com/aaai20-id9699/faplex. |
| Open Datasets | Yes | We carry out experiments on both real and synthetic graphs and demonstrate that our algorithms run much faster than the state-of-the-art algorithms. ... We show the results of random graphs with n ranging in {100, 500} and prob varying in {0.1, ..., 0.9} in Table 1. ... We also demonstrate the results of 5 real graphs which are used in (Wang et al. 2017). ... The 2nd DIMACS graphs are well-known difficult benchmarks for clique problems. ... We compare Commu Plex with D2K for networks in Stanford Large Network Dateset Collection (SNAP) (Leskovec and Krevl 2014) and Laboratory for Web Al-gorithmics (LAW) 1. |
| Dataset Splits | No | The paper describes running algorithms on entire graphs for enumeration of k-plexes and does not specify data splits like train/validation/test sets. |
| Hardware Specification | Yes | All the experiments are conducted on a computer with a Cent OS operating system an Intel 3106 CPU (1.7GHz, 8 cores) with 8G memory. |
| Software Dependencies | No | The codes are written in C++ and compiled by g++ with optimization option -O3. ... These algorithms are compiled with their makefiles and executed in single-thread mode. |
| Experiment Setup | Yes | We set the cut off time for each algorithm as 1 day (86400 seconds) for each tested instance. ... These algorithms are compiled with their makefiles and executed in single-thread mode. |