$$\varvec{\textit{KDVEM}}$$ KDVEM : a $$k$$ k -degree anonymity with vertex and edge modification algorithm

Privacy is one of the most important issues in social social network data sharing. Structure anonymization is a effective method to protect user from being reidentfied through graph modifications. The data utility of the distorted graph structure after the anonymization is a really severe problem. Reducing the utility loss is a new measurement while k-anonymity as a criterion to guarantee privacy protection. The existing anonymization algorithms that use vertex's degree modification usually introduce a large amount of distortion to the original social network graph. In this paper, we present a $$k$$k-degree anonymity with vertex and edge modification algorithm which includes two phase: first, finding the optimal target degree of each vertex; second, deciding the candidates to increase the vertex degree and adding the edges between vertices to satisfy the requirement. The community structure factors of the social network and the path length between vertices are used to evaluated the anonymization methods. Experimental results on real world datasets show that the average relative performance between anonymized data and original data is the best with our approach.