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. 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.
Type de document :
Article dans une revue
Transactions on Data Privacy, IIIA-CSIC, 2016, 9 (3), pp.26
Liste complète des métadonnées

https://hal.inria.fr/hal-01424911
Contributeur : Michaël Rusinowitch <>
Soumis le : mardi 3 janvier 2017 - 09:58:09
Dernière modification le : jeudi 11 janvier 2018 - 06:27:43
Document(s) archivé(s) le : mardi 4 avril 2017 - 13:09:57

Fichier

graph-dp-tdp.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01424911, version 1

Collections

Citation

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

Partager

Métriques

Consultations de la notice

410

Téléchargements de fichiers

101