Answers are grounded in this paper and cite their sources.
Nowadays many service providers accumulate large amounts of data. Sharing data can maximize its value, but the privacy may be leaked. Thus, the issue of privacy protection in data release has attracted the attention of academia and industry. Differential privacy has been applied to varied fields due to its excellent performance. The goal of this paper is to improve the accuracy of the published data while satisfying differential privacy. We propose an algorithm based on the hierarchical random graph (HRG) model. Considering that the users are usually interested in the data within certain communities, we apply differential privacy to the edges of a graph to various extents with the aid of community detection. Based on divide and conquer, our algorithm constructs an HRG for each community and merges sub-level HRG's into a complete one, which eliminates the inefficiency of the original algorithm when processing large-scale graphs. We treat different parts of a graph in different ways, keeping a balance between privacy and usability. According to several criteria in the experiments, our algorithm keeps the properties of the original graphs better.
No takes yet. Share an insight, caveat, or question.
Dong et al. (2017) studied this question.