A Study Of Graph Data Publication Techniques Based On Differential Privacy

The rise of social networks generates massive amounts of graph data,which is frequently collected and analyzed by data mining tools.The study of graph data can be used for knowledge discovery on the one hand and decision-making on the other.As graph data carries a large amount of user sensitive information,privacy preserving for graph data publishing becomes necessary.The existing privacy preserving technologies for graph data publishing are mainly divided into two categories:k-anonymity and differential privacy.With the development of complex networks,simple graphs are difficult to characterize the potential connections between data.Hypergraphs are increasingly being used in complex network analysis tasks in recent years due to their greater expressiveness in characterizing multi-party relationships.The existing graph data privacy preserving model is mostly based on simple graphs,and faces new challenges in the release of hypergraph data.Based on the disadvantage of existing work,we propose a more universal and robust graph data publishing method based on differential privacy.The research work and main contributions of this paper are as follows:First of all,aiming at the problem that the traditional geo-social network GSN data publishing privacy preserving method is not enough to provide strict privacy guarantee for the multi-party relationship between data,a more universal differential privacy preserving model based on hypergraph is proposed,which gives the definition of differential privacy on the neighboring hypergraph.Then,considering the social attributes and location information in the GSN data,we propose a hypergraph construction process that satisfies the differential privacy.At last,we take a more reasonable data availability metric to evaluate the accuracy of the method in the degree distribution query.Compared with the current mainstream privacy preserving methods,our method optimizes the query sensitivity calculation and reduces the noise disturbance range.Experimental results show that our method performs better in data utility and algorithm efficiency.In addition,considering the shortcomings of existing privacy preserving methods in hypergraph spectral clustering,a differential privacy-based approach is proposed,aiming to ensure the privacy at the same time maximizing the utility of hypergraph spectrum.Firstly,we give the query sensitivity calculation and proof of the hypergraph spectrum.Then,we propose two hypergraph spectrum calculation methods that satisfy the differential privacy based on different matrix perturbation mechanisms.Finally,taking into account the performance of spectral clustering,we take a more comprehensive data utility metric.The experimental results show that compared with the traditional spectrum perturbation method,our method performs better on the hypergraph clustering task and has less running time.