  The problem of finding the degeneracy of a graph is a subproblem of the
k-core decomposition problem. In this paper, we present a (1 +
epsilon)-approximate solution to the degeneracy problem which runs in O(n log
n) time, sublinear in the input size for dense graphs, by sampling a small
number of neighbors adjacent to high degree nodes. Our algorithm can also be
extended to an O(n log n) time solution to the k-core decomposition problem.
This improves upon the method by Bhattacharya et al., which implies a (4 +
epsilon)-approximate ~O(n) solution to the degeneracy problem, and our
techniques are similar to other sketching methods which use sublinear space for
k-core and degeneracy. We prove theoretical guarantees of our algorithm and
provide optimizations, which improve the running time of our algorithm in
practice. Experiments on massive real-world web graphs show that our algorithm
performs significantly faster than previous methods for computing degeneracy,
including the 2022 exact degeneracy algorithm by Li et al.
