The Research On The Publishing Algorithm In Dynamic Networks Based On Differential Privacy And Game Theory

Information networks(such as social networks,email networks,etc.)are highly valuable for data mining and analysis,but they often contain highly sensitive personal data such as social connections and personal communications records.In order to protect the privacy of individual users,the network needs to be properly sanitized before being released to third parties for public access and scientific research.In this paper,we use the differential privacy protection model to protect the private data in the network graph.In order to reduce the amount of differential privacy noise,we use hierarchical random graph(HRG)model to represent the network graph,adding noise to the connection probabilities between nodes in the graph instead of directly adding noise to the edges.In order to further control the amount of noise,we conduct community detection on the network graph before constructing the HRG.adding more noise to the connection probabilities inside the communities and less noise to those between the communities.Real-world networks are usually dynamic.In order to deal with the problem of privacy protection in dynamic networks,we propose time-window partitioning and dynamic network community detection algorithms in addition to differential privacy and the HRG model.For each time window,we release a sanitized graph.In order to deal with the challenges incurred by the dynamic features,we further divide each time window into several levels,reducing the time overhead and the cumulative error by stratified sampling and pruning similar graphs.Meanwhile,we try to keep the network structural characteristics of the time window as much as possible.We validate the proposed algorithm on two real-world datasets.Experiments show that the proposed algorithm can preserve the three essential network structural properties of the original graph under the premise of satisfying the differential privacy protection model:node degree distribution,shortest path length distribution and Top-K center point coverage.