Abstract:

With the increasing use of mass graph data in commerce and academia,it has become critical to ensure privacy when sharing and publishing graph data.However,existing anonymous privacy-preserving models struggle to balance the conflict between privacy and utility of graph data.To address this issue,a k-degree anonymity privacy preserving model based on neighbor subgraph perturbation has been proposed,which enhances both the levels of privacy preservation and data utility.To achieve k-degree anonymity privacy preservation,this model first perturbs the 1-neighbor subgraph of each node in graph data by using neighbor subgraph perturbation.This perturbation is optimized,resulting in improved perturbing efficiency and reduced data utility loss.Next,the partition of anonymous node group is optimized by using a divide-and-conquer strategy based on the degree sequence of nodes,leading to improved utility of the anonymized graph.Finally,the anonymized graph is reconstructed by editing both edges and subgraph borders to achieve k-degree anonymity privacy preservation.Comparisons and experiments have shown that the proposed model greatly improves both the overhead and security when compared to existing models and that it is able to resist both degree-based attacks and neighborhood attacks.Furthermore,the data utility is greatly improved,as evidenced by metrics such as change proportion of edges,information loss,change in the average degree of nodes,and clustering coefficient.

Key words: privacy-preserving techniques, graph structures, anonymization, k-degree anonymous, neighbor subgraph