Graph publication when the protection algorithm is available

With the popularity of social networks, the privacy issues related with social network data become more and more important. The connection information between users, as well as their sensitive attributes, should be protected. There are some proposals studying how to publish a privacy preserving graph. However, when the algorithm which generates the published graph is known by the attacker, the current protection models may still leak some connection information. In this paper, we propose a new protection model, named Semi-Edge Anonymity to protect both user's sensitive attributes and connection information even when an attacker knows the publication algorithm. Moreover, Semi-Edge Anonymity model can plug in any state-of-the-art protection model for tabular data to protect sensitive labels. We theoretically prove that on two utilities, the possible world size and the true edge ratio, the Semi-Edge Anonymity model outperforms any clustering based model which protects links. We further conduct extensive experiments on real data sets for several other utilities. The results show that our model also has better performance on these utilities than the clustering based model. ? 2013 Elsevier B.V.EI267-2858