Abstract
Recent work by Dhulipala et al. \cite{DLRSSY22} initiated the study of the k-core decomposition problem under differential privacy via a connection between low round/depth distributed/parallel graph algorithms and private algorithms with small error bounds. They showed that one can output differentially private approximate k-core numbers, while only incurring a multiplicative error of (2 +η) (for any constant η >0) and additive error of (log(n))/. In this paper, we revisit this problem. Our main result is an -edge differentially private algorithm for k-core decomposition which outputs the core numbers with no multiplicative error and O(log(n)/) additive error. This improves upon previous work by a factor of 2 in the multiplicative error, while giving near-optimal additive error. Our result relies on a novel generalized form of the sparse vector technique, which is especially well-suited for threshold-based graph algorithms; thus, we further strengthen the connection between distributed/parallel graph algorithms and differentially private algorithms.