K-anonymisation of social network by vertex and edge modification

With the rapid growth of social networks, a large quantity of social network data is being collected, and published for analysis. Privacy is one of the major issues when publishing social network data. To address the issue, several social network anonymisation approaches have been proposed. However, these methods usually introduce a large amount of distortion to the original social network graph, thus, the utility of the social network is not preserved very well. In this paper, we present a two-phase approach: in the first phase, we get the target degree of each vertex; the community structure of the social network and path length between vertices are considered when finding candidates to increase the degree of vertex to its target degree in the second phase. Experimental results on real world datasets show that the utility of the social network is well preserved with our approach.