Research On Differential Privacy Protection Technology For Frequent Subgraph Mining

Frequent graph pattern mining is a research hotspot in data mining.Frequent subgraph mining is a new research direction of frequent graph pattern mining.Finding frequent subgraphs in social networks plays an important role in understanding social interaction and studying the spread of diseases.However,it will bring the risk of privacy disclosure when mining and publishing.Thus,aiming at the privacy problem of frequent subgraph mining in static and dynamic scenes,the following two algorithms are proposed:(1)In view of static scenes,this paper proposes a more secure and effective algorithm based on differential privacy for depth first search frequent subgraph mining algorithm DP-g Span.The traditional scheme mainly uses the breadth first search mining method based on differential privacy to mine frequent subgraphs.These algorithms generally have the problems of complex support calculation and too large candidate item set,resulting in low accuracy and efficiency.Different from the past,DP-g Span algorithm realizes the rational allocation of privacy budget through a new privacy budget allocation strategy,and the pruning and truncation strategy reduces the size of candidate sets,so as to solve the shortcomings of previous algorithms.Through theoretical analysis and experimental verification,DP-gspan algorithm has better utility than the existing solutions(2)For dynamic scenes,this paper proposes a differential privacy frequent induced subgraph mining algorithm DPSR in incremental graph.In order to better balance the privacy and timeliness of statistical results,DPSR algorithm combines differential privacy in the sliding window model,and designs an appropriate privacy budget allocation strategy in the process of mining and publishing.By calculating the difference between the frequent graph pattern sets of continuous timestamp mining,it is determined that the statistical results of the current timestamp need to be published after adding noise again,or the previous results are used to approximate instead of publishing.Finally,this paper makes an experimental evaluation of DPSR algorithm.The results show that DPSR not only meet the data privacy but also complete the mining task efficiently.