DP-FT: A Differential Privacy Graph Generation With Field Theory for Social Network Data Release

Abstract

Many data analysis applications rely on social networks that contain abundant information about individuals. Nevertheless, these applications can leak private information about individuals in social networks. To protect the privacy of individuals in social networks, several approaches involving graph generation models or differential privacy were proposed for publishing a social network in place of the original graph for data analysis applications. However, these techniques can cause a serious loss of data utility, especially regarding the real social links. In this paper, we propose an approach of degree-differential privacy graph generation with field theory. The approach includes two steps for publishing a social network. The degrees of the nodes are first perturbed with the differential privacy by adding noise that follows a Laplacian distribution. Then, the edges of the social network are synthesized with field theory. We propose a field theory model for social networks by simulating the law of gravity in physics and establish the correspondence of the gravitational field in physics to the field theory model. When an edge is formed, the starting node is preferentially chosen with high probability from the nodes with high degrees, and then the ending node is selected with high probability when the interaction force between the starting node and the ending node is large. Extensive experiments over four datasets show that our approach can preserve more real social ties compared with previous approaches and will not incur a loss of structure features over the datasets, such as the degree distribution and clustering coefficients.

Keywords

• Differential privacy
• graph generation model
• privacy-preserving data publication
• social networks