Graph publishing method based on differential privacy protection

There are growing concerns surrounding the data security of social networks because large amount of user information and sensitive data are collected. Differential privacy is an effective method for privacy protection that can provide rigorous and quantitative protection. Concerning the application of differential privacy in social networks,this paper analyzes current trends of research and provides some background information including privacy protection standards and noise mechanisms.Focusing on the privacy protection of social network data publishing,a graph-publishing model is designed to provide differential privacy in social networks via three steps: Firstly,according to the features of social network where two nodes that possess certain common properties are associated with a higher probability,a raw graph is divided into several disconnected sub-graphs,and correspondingly dense adjacent matrixes and the number of bridges are obtained. Secondly,taking the advantage of quad-trees,dense region exploration of the adjacent matrixes is conducted. Finally,using an exponential mechanism and leaf nodes of quad-trees,an adjacent matrix of the sanitized graph is reconstructed. In addition,a set of experiments is conducted to evaluate its feasibility,availability and strengths using three analysis techniques: degree distribution,shortest path,and clustering coefficients.