A Privacy-Preserving Approach in Friendly-Correlations of Graph Based on Edge-Differential Privacy

摘要

It is a challenging problem to preserve friendly-correlations between individuals when publishing social network data. To alleviate this problem, uncertain graph has been presented recently. The main idea of uncertain graph is converting an original graph into an uncertain form, where the friendly-correlations of the graph are associated with probabilities. However, the existing methods of uncertain graph lack rigorous guarantees of privacy and rely on the assumption of adversary's knowledge. In this paper, we introduced a general model for constructing uncertain graphs. Then, we proposed an Uncertain Graph based on Differential Privacy algorithm (UGDP algorithm) under the general model which provides a rigorous privacy guarantee against powerful adversaries, and we define a new metric to measure privacy for different algorithms. Finally, we evaluate some uncertain algorithms in privacy and utility, the result shows that UGDP algorithm satisfies edge-differential privacy and the data utility is acceptable. The conclusions are that the UGDP algorithm has better privacy preserving than the (k, epsilon)-obfuscation algorithm, and better data utility than the RandWalk algorithm.