Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Computing (1+epsilon)-Approximate Degeneracy in Sublinear Time
Authors: Valerie King, Alex Thomo, Quinton Yong
IJCAI 2023 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experiments on massive real-world web graphs show that our algorithm performs significantly faster than previous methods for computing degeneracy. We compare our solution to the (1 + )-approximate algorithm of [Farach-Colton and Tsai, 2016] and the Semi Deg+ algorithm from [Li et al., 2022] on massive real-world webgraphs and show that our algorithm is faster than both on all datasets. |
| Researcher Affiliation | Academia | Valerie King , Alex Thomo , Quinton Yong University of Victoria, Victoria, Canada EMAIL |
| Pseudocode | Yes | Algorithm 1 Approximate Degeneracy(G, ϵ, c) |
| Open Source Code | Yes | An implementation of our method is available at https://github. com/Quinton Yong/NESD |
| Open Datasets | Yes | We use the datasets twitter-2010, sk-2005, gsh-2015, uk2014, and clueweb12 from the Laboratory of Web Algorithmics [Boldi and Vigna, 2004; Boldi et al., 2011; Boldi et al., 2014], and the characteristic of each graph is illustrated in Table 1. |
| Dataset Splits | No | The paper does not provide specific training/validation/test dataset splits. The experiments involve running a graph algorithm on entire graphs, not machine learning models with traditional data splits. |
| Hardware Specification | Yes | the experiments were run on Amazon EC2 instances with the r5.24xlarge instance size (96 v CPU, 768GB memory) running Linux. |
| Software Dependencies | Yes | The algorithms used in the experiments were implemented in Java 11 |
| Experiment Setup | Yes | We experiment with four different values of , namely 0.5, 0.25, 0.1, and 0.05, to illustrate the varying approximation accuracies of our algorithm. The value of c did not have a major impact on the results since the probability of correctness is high with n being large in all of the datasets. So, we use c = 0.5 for all experiments. |