Publishing Node Strength Distribution With Node Differential Privacy

Abstract

The challenge of graph data publishing under node-differential privacy mainly comes from the high sensitivity of the query. Compared with edge-differential privacy that can only protect the relationship between people, node-differential privacy can protect both the relationship between people and personal information. Therefore, Node-differential privacy must pay attention to the protection of personal information. This paper studies the release of node strength distribution under node-differential privacy by reducing sensitivity. We propose two algorithms to publish node strength distribution: Alternate-histogram (ALT-histogram) and Density-histogram (DEN-histogram). Experimental results show that compared with the existing node strength histogram publishing algorithm, our proposed algorithm has advantages in L1-error and KS-distance, make the noise node strength distribution closer to that of the original graph. We also propose an introspective analysis to understand the influence of the projection algorithm on the node strength distribution, experiments to prove that the projection algorithm plays an important role in the node strength distribution.

Keywords

• Differential privacy
• private graph publishing
• node strength