A novel approach to achieving ?-anonymization for social network privacy preservation based on vertex connectivity

Social networks have been widely used, providing people with great convenience but also yielding potential risk of privacy disclosure. To prevent attacks based on background information or query that may expose users´ privacy, we propose a method to achieve k-anonymization for network graphs. The concept of similarity matrix and that of the distance between a vertex and a cluster are defined based on vertex connectivity. On this basis, we present a clustering-based graph partitioning algorithm to obtain the K-anonymized graph of a certain network graph. Simulation experiments are conducted to analyze and verify the effectiveness of our algorithm.