Preservation of Structural Properties in Anonymized Social Networks

Social networks such as Facebook, LinkedIn, or Twitter have nowadays a global reach that surpassed all previous expectations. Many social networks gather confidential information of their users, and as a result, the privacy in social networks has become a topic of general interest. To defend against privacy violations, several social network anonymization models were introduced. In this paper, we empirically study how well several structural properties of a social network are preserved through an anonymization process. We first anonymize several real and synthetic social networks using the k-anonymous cluster social network model, and then we compare how well structural properties such as diameter, centrality measures, clustering coefficients, and topological indices are preserved between the original networks and their anonymized versions. Our experiments show that there are correlations between the structural properties’ values obtained from the original network and from the corresponding anonymized networks. Preserving such graph properties through anonymization might be extremely important / essential for subsequent graph-mining of the anonymized networks.