Differentially Private Publication of Social Graphs at Linear Cost - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2015

Differentially Private Publication of Social Graphs at Linear Cost

Résumé

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.
Fichier principal
Vignette du fichier
asonam068-nguyen.pdf (130.63 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01179528 , version 1 (22-07-2015)

Identifiants

  • HAL Id : hal-01179528 , version 1

Citer

Huu Hiep Nguyen, Abdessamad Imine, Michaël Rusinowitch. Differentially Private Publication of Social Graphs at Linear Cost. ASONAM 2015, Aug 2015, Paris, France. ⟨hal-01179528⟩
258 Consultations
345 Téléchargements

Partager

Gmail Facebook X LinkedIn More