Abstract:In social networks, anonymization processing is required to prevent the leakage of user privacy before user data is released. In this study, the social network anonymization is modeled as the k-degree anonymization of graphs given the privacy attack with the background of node degrees. The major method is to add as few edges or nodes as possible to the graph to meet the degree-anonymization requirements, and by doing this, the structural characteristics of the original graph are expected to be maintained to a large extent. At present, the edge-adding algorithms cannot well retain the basic structural characteristics such as the average path length, while the edge-node adding algorithms can better retain the structural characteristics of the original graph after adding many edges or nodes. Considering this situation, this study proposes an improved algorithm combining the two algorithms. Firstly, the greedy algorithm is used to generate the anonymity sequence, and then the edge-adding operation is performed on the basis of the community structure. The anonymization requirements of nodes with higher anonymity costs than the average anonymity costs are satisfied first, and node adding can be applied to the graph when edge adding cannot complete the anonymization. The experimental results of actual datasets show that the new algorithm can better retain several typical structural characteristics of the graph, and the number of added edges or nodes is less.