Premium
Sensitivity reduction of degree histogram publication under node differential privacy via mean filtering
Author(s) -
Lan Sun,
Xin Huang,
Yingjie Wu,
Yongyi Guo
Publication year - 2019
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.5621
Subject(s) - histogram , degree (music) , sensitivity (control systems) , node (physics) , differential privacy , computer science , graph , information sensitivity , data publishing , data mining , publishing , artificial intelligence , theoretical computer science , computer security , image (mathematics) , engineering , law , physics , structural engineering , electronic engineering , acoustics , political science
Summary Publication of nodes' degree information in the form of histogram provides useful information about the graph as well as the risk of privacy disclosure. Under the robust protection of node‐differential privacy (node‐DP), publishing result's accuracy mainly depends on the global sensitivity of this publishing task. Thus, the reduction of sensitivity is of great importance. Existing methods for degree histogram publication under node‐DP are mostly based on limitation of maximum degree, whose sensitivity is still high, leading an unbearable noise scale. In this paper, we innovatively propose a method to tackle this issue. Firstly, we introduce mean filtering to process the histogram, almost halve the original sensitivity. Then, we use a series of techniques to further improve publishing accuracy, instituting a complete workflow for degree histogram publication under node‐DP. Experimental results show that our method effectively improves the accuracy.