Fast Solving Maximum Weight Clique Problem in Massive Graphs
Authors: Shaowei Cai, Jinkun Lin
IJCAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experiments on massive graphs from various applications show that, Fast WClq finds better solutions than state of the art algorithms while the run time is much less. |
| Researcher Affiliation | Academia | 1State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing, China 2Key Laboratory of High Confidence Software Technologies, Peking University, Beijing, China |
| Pseudocode | Yes | The pseudo code of Fast WClq is shown in Algorithm 1. Algorithm 1: Fast WClq (G, cutoff) ... Algorithm 2: Choose Add V ertex(Cand Set, k) |
| Open Source Code | No | The paper states that "Fast WClq is implemented in C++" but does not provide any link or explicit statement about releasing its source code. |
| Open Datasets | Yes | The benchmarks in our experiments were originally from the Network Data Repository online [Rossi and Ahmed, 2015],2 including biological networks, collaboration networks, facebook networks, interaction networks, infrastructure networks, amazon recommend networks, retweet networks, scientific computation networks, social networks, technological networks, and web link networks. 2http://www.graphrepository.com/networks.php |
| Dataset Splits | No | The paper does not provide explicit details about train/validation/test dataset splits, specific percentages, or sample counts. It refers to using "benchmarks" but not how data within these benchmarks was partitioned for training or validation. |
| Hardware Specification | Yes | The experiments are carried out on a workstation under Ubuntu Linux 14.04, using 2 cores of Intel i7-4710MQ CPU @ 2.50 GHz and 32 GByte RAM. |
| Software Dependencies | Yes | The experiments are carried out on a workstation under Ubuntu Linux 14.04, using 2 cores of Intel i7-4710MQ CPU @ 2.50 GHz and 32 GByte RAM. All algorithms are complied with g++ version 4.7 with -O3 option. |
| Experiment Setup | Yes | Parameters k0 and kmax for dynamic BMS heuristic are set to 4 and 64 (=26). The cutoff time ( ct ) for Fast WClq is 100 seconds per run. For LSCC+BMS, we test it under two cutoff time, 100 and 1000 seconds. For the exact algorithm Max WClq, we run it once on each graph with a cutoff time of one hour. |