Differentially Private Publication of Social Graphs at Linear Cost

Hiep H. Nguyen 1 Abdessamad Imine 1 Michaël Rusinowitch 1
1 CASSIS - Combination of approaches to the security of infinite states systems
FEMTO-ST - Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174), 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, a large body of existing works on differentially private release of graphs have not answered the question about the upper bounds of privacy budgets. In this paper, for the first time, such a bound is provided. We prove that with a privacy budget of O(log n), there exists an algorithm capable of releasing a noisy output graph with edge edit distance of O(1) against the true graph. At the same time, the complexity of our algorithm Top-m Filter is linear in the number of edges m. This lifts the limits of the state-of-the-art, which incur a complexity of O(n^2) where n is the number of nodes and runnable only on graphs having n of tens of thousands.
Type de document :
Communication dans un congrès
ASONAM 2015, Aug 2015, Paris, France. 〈http://asonam.cpsc.ucalgary.ca/2015/〉
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01179528
Contributeur : Hiep H. Nguyen <>
Soumis le : mercredi 22 juillet 2015 - 16:55:01
Dernière modification le : vendredi 6 juillet 2018 - 15:06:10
Document(s) archivé(s) le : vendredi 23 octobre 2015 - 11:21:58

Fichier

asonam068-nguyen.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01179528, version 1

Citation

Hiep H. Nguyen, Abdessamad Imine, Michaël Rusinowitch. Differentially Private Publication of Social Graphs at Linear Cost. ASONAM 2015, Aug 2015, Paris, France. 〈http://asonam.cpsc.ucalgary.ca/2015/〉. 〈hal-01179528〉

Partager

Métriques

Consultations de la notice

435

Téléchargements de fichiers

191