Rank-Label Anonymization for the Privacy-Preserving Publication of a Hypergraph Structure

Abstract

Social networks are often published in the form of a simple graph. The simple graph representation of a social graph shows the dyadic relationship among the social entities whereas it is unable to efficiently represent the relationship among more than two entities, such as the relationship found in the social groups. This type of relationship is called super-dyadic relationship, and it can be effectively represented by a hypergraph model. This work proposes an anonymization scheme called rank-label anonymization for the privacy-preserving publication of a hypergraph structure. Here, an attack model called rank-label attack is proposed, and an anonymization solution is provided to counter this attack. The percentage of disclosure risk shows that the rank-label attack is stronger than the existing rank attack. We propose a method based on sequential clustering to achieve rank-label anonymization called sequential rank-label anonymization (SA). Another algorithm called greedy rank-label anonymization (GA) is also proposed. The quality of the anonymization solution reported by SA and GA is compared with the help of normalized anonymization cost (NCost). Results show that the NCost reported by SA is less than that of GA for both Adult and MAG-10 datasets. In Adult dataset, approximately 58% and 62% reduction in the average execution time of GA and SA are obtained than that of a general-purpose computing system due to the use of a high-performance computing system. In MAG-10 dataset, this average reduction percentage is reported to be 56% for GA and 53% for SA. The time complexity of SA is found to be O(n4) whereas it is O(n3) in case of GA.

Keywords

• Anonymity
• hypergraph
• sequential clustering
• privacy preservation