Research On The Technology Of Graph Data Publication With Differential Privacy

The rapid development of the Internet and information technology has led to many new industries and service application models,such as social networks,bike-sharing,Didi Taxi,and Internet medical services and so on.By collecting users' information on a large scale,these new information systems can provide users with more accurate,personalized and diversified services with big data analysis technology.However,these collected information often contains a large amount of users' sensitive information,such as personal interests,locus of motion,consumption habits,health records,etc.The release and analysis of these information will bring a great threat to user privacy.How to publish and mine these data securely under the premise of protecting user privacy is a core issue that needs to be solved to maximize its potential value.Differential privacy technology overcomes many shortcomings of traditional privacy protection models,which has become a standard in the field of privacy protection and been widely used in the field of traditional data analysis.But there is little research in the field of graph data.This paper focuses on the securely publishing of sensitive graph data generated by new information systems such as social networks.The statistical feature release of graph data and the construction of graph generation model under the constraints of differential privacy are studied,and the following results are achieved:1.Aiming at the high sensitivity problem of graph degree distribution algorithm under the node differential privacy,a sequence edge-removal(SER)projection method is proposed,which reduces the sensitivity while retaining more edges of the original graph and reducing errors between the projection graph and the original graph.Based on the SER projection method,two histogram publishing mechanisms of degree distribution are proposed,and they are theoretically proved to satisfy the definition of node differential privacy.The experiment results show that provided the same level of privacy preservation,the proposed histogram publishing mechanism based on the SER method can describe the degree distribution of the original data more accurately,and thus improve the usability of the published data.2.Aiming at the problem that graph data size grows dynamically with time in practical application,the existing SER algorithm is adjusted to avoid the inconsistency of the result graphs after multiple projections on the same graph.On this basis,a degree histogram publishing method(SER-continual)for incremental graph data under node differential privacy is proposed,and the method is theoretically proved to satisfy the definition of node differential privacy.Simulation experiments show that the SER-continual method effectively reduces errors of the histogram released and avoids waste of computing resources.3.For the securely publishing problem of graph data in non-interactive mode,an optimized random response algorithm(ORR)is given by limiting the value of random response probability.Based on this,by combining classical differential privacy,secure multi-party computation and local differential privacy,a synthetic graph generation method(LDPGM)is proposed.It is theoretically proved that the proposed method satisfies the definitions of differential privacy and local differential privacy.The simulation experiments show that the synthetic graph generation method under differential privacy can describe the degree distribution and clustering properties of real data well.Meanwhile,it can effectively reduce the errors of synthetic graphs and improve the accuracy of data analysis results based on synthetic graphs.