Visible to the public Publishing Graph Degree Distribution with Node Differential Privacy

TitlePublishing Graph Degree Distribution with Node Differential Privacy
Publication TypeConference Paper
Year of Publication2016
AuthorsDay, Wei-Yen, Li, Ninghui, Lyu, Min
Conference NameProceedings of the 2016 International Conference on Management of Data
Conference LocationNew York, NY, USA
ISBN Number978-1-4503-3531-7
Keywordscomposability, degree distribution, Differential privacy, Human Behavior, private graph publishing, pubcrawl, Resiliency, Scalability

Graph data publishing under node-differential privacy (node-DP) is challenging due to the huge sensitivity of queries. However, since a node in graph data oftentimes represents a person, node-DP is necessary to achieve personal data protection. In this paper, we investigate the problem of publishing the degree distribution of a graph under node-DP by exploring the projection approach to reduce the sensitivity. We propose two approaches based on aggregation and cumulative histogram to publish the degree distribution. The experiments demonstrate that our approaches greatly reduce the error of approximating the true degree distribution and have significant improvement over existing works. We also present the introspective analysis for understanding the factors of publishing the degree distribution with node-DP.

Citation Keyday_publishing_2016