Paper 2016/745

Novel differentially private mechanisms for graphs

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


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.

Available format(s)
Publication info
Preprint. MAJOR revision.
anonymityapplicationsinformation theory
Contact author(s)
baptiste olivier @ orange com
2016-08-02: received
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.