Preserving Utility in Social Network Graph Anonymization

To protect from privacy disclosure, the social network graph is modified in order to hide the information that potentially be used to disclose person´s identity. However, when the social network graph is changed, it is a great challenge to balance between the privacy gained and the loss of data utility. In this paper, we address this problem. We propose a new graph topological-based metric to improve utility preservation in social network graph anonymization. We compare the proposed approach with the amount-of-edge-change metric that popularly used in most of previous works. Experimental evaluation shows that our approach generates anonymized social network with improved utility preservation.