Skip to Main content Skip to Navigation
Journal articles

Network Structure Release under Differential Privacy

Hiep Nguyen 1 Abdessamad Imine 1 Michael Rusinowitch 1
1 PESTO - Proof techniques for security protocols
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : The problem of private publication of graph data has attracted a lot of attention recently. The prevalence of differential privacy makes the problem more promising. However, the problem is challenging because of the huge output space of noisy graphs, up to $2^{n(n-1)/2}$. In addition, a large body of existing schemes on differentially private release of graphs are not consistent with increasing privacy budgets and do not clarify the upper bounds of privacy budgets. In this paper, we categorize the state-of-the-art in two main groups: direct publication schemes and model-based publication schemes. On the one hand, we explain why model-based publication schemes are not consistent and are suitable only in scarce regimes of privacy budget. On the other hand, we prove that with a privacy budget of $O(ln\,n)$, there exist direct publication schemes capable of releasing noisy output graphs with edge edit distance of $O(1)$ against the true graph. We introduce the new linear scheme Top-m-Filter (TmF) and improve the existing technique EdgeFlip. Both of them exhibit consistent behaviour with increasing privacy budgets while the model-based publication schemes do not. As for better scalability, we also introduce HRG-FixedTree, a fast permutation sampling, to learn the Hierarchical Random Graph (HRG) model. Thorough comparative evaluation on a wide range of graphs provides a panorama of the state-of-the-art's performance as well as validates our proposed schemes.
Complete list of metadata
Contributor : Michaël Rusinowitch Connect in order to contact the contributor
Submitted on : Tuesday, January 3, 2017 - 9:58:09 AM
Last modification on : Wednesday, November 3, 2021 - 7:56:59 AM
Long-term archiving on: : Tuesday, April 4, 2017 - 1:09:57 PM


Files produced by the author(s)




Hiep Nguyen, Abdessamad Imine, Michael Rusinowitch. Network Structure Release under Differential Privacy. Transactions on Data Privacy, IIIA-CSIC, 2016, 9 (3), pp.26. ⟨10.5555/3121413.3121415⟩. ⟨hal-01424911⟩



Record views


Files downloads