Cycle Counting under Local Differential Privacy for Degeneracy-bounded Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929516808503296 |
|---|---|
| author | Hillebrand, Quentin Suppakitpaisarn, Vorapong Shibuya, Tetsuo |
| author_facet | Hillebrand, Quentin Suppakitpaisarn, Vorapong Shibuya, Tetsuo |
| contents | 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 $\ell_2$-error of these algorithms is $Ω(n^{1.5})$, where $n$ is the number of nodes in the graph. When parameterized by the number of cycles of length four ($C_4$), the best existing triangle counting algorithm has an error of $O(n^{1.5} + \sqrt{C_4}) = O(n^2)$. In this paper, we introduce an algorithm with an expected $\ell_2$-error of $O(δ^{1.5} n^{0.5} + δ^{0.5} d_{\max}^{0.5} n^{0.5})$, where $δ$ is the degeneracy and $d_{\max}$ is the maximum degree of the graph. For degeneracy-bounded graphs ($δ\in Θ(1)$) commonly found in practical social networks, our algorithm achieves an expected $\ell_2$-error of $O(d_{\max}^{0.5} n^{0.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 $\ell_2$-error, namely $O(δ^{(k-2)/2} d_{\max}^{0.5} n^{(k-2)/2} + δ^{k/2} n^{(k-2)/2})$ or $O(d_{\max}^{0.5} n^{(k-2)/2}) = O(n^{(k-1)/2})$ for degeneracy-bounded graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_16688 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Cycle Counting under Local Differential Privacy for Degeneracy-bounded Graphs Hillebrand, Quentin Suppakitpaisarn, Vorapong Shibuya, Tetsuo Cryptography and Security Data Structures and Algorithms 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 $\ell_2$-error of these algorithms is $Ω(n^{1.5})$, where $n$ is the number of nodes in the graph. When parameterized by the number of cycles of length four ($C_4$), the best existing triangle counting algorithm has an error of $O(n^{1.5} + \sqrt{C_4}) = O(n^2)$. In this paper, we introduce an algorithm with an expected $\ell_2$-error of $O(δ^{1.5} n^{0.5} + δ^{0.5} d_{\max}^{0.5} n^{0.5})$, where $δ$ is the degeneracy and $d_{\max}$ is the maximum degree of the graph. For degeneracy-bounded graphs ($δ\in Θ(1)$) commonly found in practical social networks, our algorithm achieves an expected $\ell_2$-error of $O(d_{\max}^{0.5} n^{0.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 $\ell_2$-error, namely $O(δ^{(k-2)/2} d_{\max}^{0.5} n^{(k-2)/2} + δ^{k/2} n^{(k-2)/2})$ or $O(d_{\max}^{0.5} n^{(k-2)/2}) = O(n^{(k-1)/2})$ for degeneracy-bounded graphs. |
| title | Cycle Counting under Local Differential Privacy for Degeneracy-bounded Graphs |
| topic | Cryptography and Security Data Structures and Algorithms |
| url | https://arxiv.org/abs/2409.16688 |