Preserving privacy in social network graph with K-anonymize degree sequence generation

The notion of being connected is primal in the modern world. Everyday people spend a great amount of their time in the virtual world through various online social networking sites. As a result a huge amount of personal information is being exchanged over the social network making them top of the interest to researchers from every field, various application developing companies, advertising companies and even governments. Analysis of these graphs helps discover invaluable knowledge. But this boon does not come without curse. Many invasive adversaries threat the confidentiality of this private information making the users vulnerable to being exposed and identified. So preserving privacy while publishing the social network graph data is one the most important concerns in today´s world. Different technique has been adopted to anonymize social network data before publishing. In this paper we have proposed an iterative algorithm to generate k-anonymize vertex degree sequence of a given social network graph in order to protect the graph against passive attack. We have applied our method to some social network graph datasets and demonstrated their efficiency in preventing vertex re-identification attacks where an adversary has background knowledge about the degree of the target vertex.