Anonymization of attributed social graph using anatomy based clustering

A social graph is a common way to publish a social network, but such publication poses privacy risks. In this paper, we use attributed social graph as a graph model to represent the original social network. Therefore, anonymization of descriptive as well as structural data is essential to meet the privacy requirement. Cluster based anonymization is one of the anonymization approaches that provides privacy preservation in social network publication. Though most of the previous work like SaNGreeA (SNG) and Sequential Clustering (SC) employ generalization based clustering, we propose an Anatomy based Clustering (AC) that retains the data originality since it doesn't suppress or generalize any value. Therefore, the proposed approach provides higher utility than the existing approaches. Consequently, the information loss in AC is found to be lower than SNG and SC. We propose a Modified Anatomy based Clustering (MAC) which ensures better preservation of ground-truth community than AC. The algorithms are tested on Attributed Networks (ANs) that are created by the proposed Network Generator algorithm. According to information loss and information gain based community preservation, MAC is found to be the best among the four algorithms i.e., SNG, SC, AC, and MAC.