Generating Differentially Private Networks with a Modified Erdős-Rényi Model
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918152876589056 |
|---|---|
| author | Rao, Huaiyuan Hawkins, Calvin Benvenuti, Alexander Hale, Matthew |
| author_facet | Rao, Huaiyuan Hawkins, Calvin Benvenuti, Alexander Hale, Matthew |
| contents | Differential privacy has been used to privately calculate numerous network properties, but existing approaches often require the development of a new privacy mechanism for each property of interest. Therefore, we present a framework for generating entire networks in a differentially private way. Differential privacy is immune to post-processing, which allows for any network property to be computed and analyzed for a private output network, without weakening its protections. We consider undirected networks and develop a differential privacy mechanism that takes in a sensitive network and outputs a private network by randomizing its edge set. We prove that this mechanism does provide differential privacy to a network's edge set, though it induces a complex distribution over the space of output graphs. We then develop an equivalent privacy implementation using a modified Erdős-Rényi model that constructs an output graph edge by edge, and it is efficient and easily implementable, even on large complex networks. Experiments implement $\varepsilon$-differential privacy with $\varepsilon=2.5$ when computing graph Laplacian spectra, and these results show the proposed mechanism incurs $49.34\%$ less error than the current state of the art. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_25431 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Generating Differentially Private Networks with a Modified Erdős-Rényi Model Rao, Huaiyuan Hawkins, Calvin Benvenuti, Alexander Hale, Matthew Optimization and Control Systems and Control Differential privacy has been used to privately calculate numerous network properties, but existing approaches often require the development of a new privacy mechanism for each property of interest. Therefore, we present a framework for generating entire networks in a differentially private way. Differential privacy is immune to post-processing, which allows for any network property to be computed and analyzed for a private output network, without weakening its protections. We consider undirected networks and develop a differential privacy mechanism that takes in a sensitive network and outputs a private network by randomizing its edge set. We prove that this mechanism does provide differential privacy to a network's edge set, though it induces a complex distribution over the space of output graphs. We then develop an equivalent privacy implementation using a modified Erdős-Rényi model that constructs an output graph edge by edge, and it is efficient and easily implementable, even on large complex networks. Experiments implement $\varepsilon$-differential privacy with $\varepsilon=2.5$ when computing graph Laplacian spectra, and these results show the proposed mechanism incurs $49.34\%$ less error than the current state of the art. |
| title | Generating Differentially Private Networks with a Modified Erdős-Rényi Model |
| topic | Optimization and Control Systems and Control |
| url | https://arxiv.org/abs/2509.25431 |