Research On Publishing Graph Histograms With Differential Privacy

As a form of information expression,graphs can intuitively describe the connections between things,such as social networks.In order to fully exploit potential application value of the data,it is necessary to publish graph data for analysis.In the process,we need to ensure that sensitive information in the data is not leaked.As a rigorous and theoretically proven privacy protection technology,differential privacy can protect data security while maximizing data availability.Therefore,in recent years,many researchers have conducted extensive research on publishing graph data with differential privacy.Histogram is an important form of data release with differential privacy,and the degree of nodes is one of the significant statistical features of graph.Therefore,the degree distribution publishing based on histogram has attracted much attention and great progress has been made.In the existing degree distribution query research,the global sensitivity of the query problem can be effectively reduced by using graph projection method,but a lot of original topological information will be lost.At the same time,although the degree distribution can well reflect the correlation information in the graph,it is difficult to measure the importance of the nodes to a large extent,especially in the weighted network graphs.Based on the analysis of the above problems,this thesis puts forward the corresponding solutions.The specific research contents are as follows:(1)Aiming at the issue of publishing node degree distribution,the graph projection strategy is improved to preserve more topological information in the graph.In addition,a histogram partitioning algorithm for adaptive subsets is proposed to improve the accuracy of publishing node degree distribution histogram with node differential privacy.(2)Further,the issue of publishing node strength histogram is proposed according to the actual demand,and the global sensitivity bound of the problem is theoretically reduced with edge differential privacy.t-Bounded-Buckets-Hist method is proposed to publish high-precision approximate histograms,including histogram reconstruction algorithms and optimization strategies with differential privacy.Extensive experiments have been conducted on several real world datasets to compare our proposed methods with other existing methods.The experimental results demonstrate that our approaches greatly reduce the error of approximating the true degree distribution and have significant improvement over existing studies.