Social Network Anonymization via Local-perturbing Approach

Abstract

Social networks provide a large amount of social network data, which is collected, studied and distributed for various purposes. Because social network data usually contains sensitive personal information, it needs to be anonymized before publication. Many data anonymization methods have been proposed to protect the privacy of individuals; but most methods were proposed for general purposes and suffer the problem of excessive information loss when they are used for specific purposes. In this paper, we focus on the problem of improving data utility when applying privacy-preserving methods to the original data for protection privacy. We propose two novel local-perturbing methods: one is based on the k-anonymity model; the other is based on a randomization model. Both methods can achieve the same privacy levels as k-anonymity model while minimizing the impact on community structure. We evaluate the performance of our methods by testing three real-world datasets. Experimental results show that both methods loss less community structure information compared to existing methods.