Paper 2016/745

Novel differentially private mechanisms for graphs

Solenn Brunet, Sébastien Canard, Sébastien Gambs, and Baptiste Olivier

Abstract

In this paper, we introduce new methods for releasing differentially private graphs. Our techniques are based on a new way to distribute noise among edges weights. More precisely, we rely on the addition of noise whose amplitude is edge-calibrated and optimize the distribution of the privacy budget among subsets of edges. The generic privacy framework that we propose can capture all privacy notions introduced so far in the literature to release graphs in a differentially private manner. Furthermore, experimental results on real datasets show that our methods outperform the standard existing techniques, in particular in terms of the preservation of utility. In addition, these experiments show that our mechanisms guarantee epsilon-differential privacy for a reasonable level of privacy epsilon, while preserving the spectral information of the input graph.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MAJOR revision.
Keywords
anonymityapplicationsinformation theory
Contact author(s)
baptiste olivier @ orange com
History
2016-08-02: received
Short URL
https://ia.cr/2016/745
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/745,
      author = {Solenn Brunet and Sébastien Canard and Sébastien Gambs and Baptiste Olivier},
      title = {Novel differentially private mechanisms for graphs},
      howpublished = {Cryptology {ePrint} Archive, Paper 2016/745},
      year = {2016},
      url = {https://eprint.iacr.org/2016/745}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.