Network Structure Release under Differential Privacy - Archive ouverte HAL Access content directly
Journal Articles Transactions on Data Privacy Year : 2016

Network Structure Release under Differential Privacy

(1) , (1) , (1)
Hiep Nguyen
Abdessamad Imine
  • Function : Author
  • PersonId : 755724
  • IdRef : 114367426


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.
Fichier principal
Vignette du fichier
graph-dp-tdp.pdf (488.27 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-01424911 , version 1 (03-01-2017)



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



Gmail Facebook Twitter LinkedIn More