Alpha-anonymization techniques for privacy preservation in social networks

Rapid growth and development of social networks has attracted the interest of the scientific community to utilize these huge datasets for research purpose. However, preserving the privacy of the users in the published data has also become an important concern. An adversary with very little background knowledge about the actors can extract personal information from the published data. To prevent such type of attacks, different anonymization models have been proposed for relational micro-data, which are further extended and adjusted to handle social network data. Preserving the structural properties of the raw graph is one of the most important aspects of social network anonymization. In this paper, we propose an (α, k) anonymity model based on the eigenvector centrality of the nodes present in the raw graph. We further extend the (α, k) anonymity model to propose (α, l) diversity model and (α, c, l) diversity model, which can also protect the sensitive attribute values associated with a particular actor. For anonymization purpose, we applied the noise node addition technique to generate the anonymized graphs. We tested our proposed algorithms with both synthetic dataset and real dataset. The results obtained show the effectiveness of our proposed algorithm in preserving the structural property of the raw graph. Our proposed methods add noise nodes efficiently so that they have minimal social importance.