2024/09/25 by Quentin Hillebrand, Hillebrand, Quentin, Vorapong Suppakitpaisarn +3 · 1 citation
Computer Science · #Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #Distributed systems and fault tolerance #FOS: Computer and information sciences #Optimization and Search Problems #Privacy-Preserving Technologies in Data
paper · pdf · doi:10.48550/arxiv.2409.16688
openalex publication_date 2024/09/25 · openalex created_date 2024/10/27 · openalex updated_date 2026/07/28
We propose an algorithm for counting the number of cycles under local differential privacy for degeneracy-bounded input graphs. Numerous studies have focused on counting the number of triangles under the privacy notion, demonstrating that the expected ℓ2-error of these algorithms is Ω(n1.5), where n is the number of nodes in the graph. When parameterized by the number of cycles of length four (C4), the best existing triangle counting algorithm has an error of O(n1.5 + √(C4)) = O(n2). In this paper, we introduce an algorithm with an expected ℓ2-error of O(δ1.5 n0.5 + δ0.5 dmax0.5 n0.5), where δ is the degeneracy and dmax is the maximum degree of the graph. For degeneracy-bounded graphs (δ∈ Θ(1)) commonly found in practical social networks, our algorithm achieves an expected ℓ2-error of O(dmax0.5 n0.5) = O(n). Our algorithm's core idea is a precise count of triangles following a preprocessing step that approximately sorts the degree of all nodes. This approach can be extended to approximate the number of cycles of length k, maintaining a similar ℓ2-error, namely O(δ(k-2)/2 dmax0.5 n(k-2)/2 + δk/2 n(k-2)/2) or O(dmax0.5 n(k-2)/2) = O(n(k-1)/2) for degeneracy-bounded graphs.