An Improved Privacy Preserving Algorithm for Publishing Social Network Data

With the rapid growth of social networks, privacy issues have been raised for using or sharing data including user´s information. Simply removing the identities of the vertices before publishing the social network data is considered an ill-advised practice due to privacy concerns, because the structure of the graph itself can reveal the identities of individuals. To mitigate this problem, a so-called graph k-degree anonymous method has been proposed in recent studies, in which the structure of the original graph is modified to ensure that there are at least k nodes having the same degree for each degree number in the modified graph. However, this approach arouses two key issues: the protecting algorithm has to be efficient especially for conducting on a great amount of graph data, and the modifications of the original graph should be minimized for keeping the data utility. To deal with these issues, we introduce a measurement for the modification cost of anonymizing a graph, and devise a novel privacy preserving algorithm for publishing social network data based on a new degree sequence partition algorithm. We conduct the algorithm on several real-world datasets. The experimental results show that the algorithm improve the performance of anonymizing the social network data and reduced the modifications of the original graph data.