Cryptology ePrint Archive: Report 2016/745

Novel differentially private mechanisms for graphs

Solenn Brunet and Sébastien Canard and 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.

Category / Keywords: foundations / anonymity, applications, information theory

Date: received 29 Jul 2016

Contact author: baptiste olivier at orange com

Available format(s): PDF | BibTeX Citation

Version: 20160802:210123 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]