Abstract
With the popularity of cloud computing, many companies would outsource their social network data to a cloud service provider, where privacy leaks have become a more and more serious problem. However, most of the previous studies have ignored an important fact, i.e., in real social networks, users possess various attributes and have the flexibility to decide which attributes of their profiles are sensitive attributes by themselves. These sensitive attributes of the users should be protected from being revealed when outsourcing a social network to a cloud service provider. In this paper, we consider the problem of resisting privacy attacks with neighborhood information of both network structure and labels of one-hop neighbors as background knowledge. To tackle this problem, we propose a Global Similarity-based Group Anonymization (GSGA) method to generate a anonymized social network while maintaining as much utility as possible. We also extensively evaluate our approach on both real data set and synthetic data sets. Evaluation results show that the social network anonymized by our approach can still be used to answer aggregation queries with high accuracy.