A k-Anonymization Algorithm on Social Network Data that Reduces Distances between Nodes

To provide social network data (SN) data to researchers for data analysis, protecting user privacy via anonymization is necessary. One anonymization metric for SN data called k-neighbor focuses on the neighborhood subgraphs, which, for each node, consists of the node´s neighbor nodes. This metric ensures that the neighborhood subgraph of every node in the anonymized graph is isomorphic to at least k other neighborhood subgraphs, however, the existing algorithm to realize k-neighbor does not consider case that adding noise edges for anonymization may drastically change the distances of some pairs of nodes, which in turn may alter the structure of the original graph. To solve this problem, we propose an algorithm that focuses on a method to add noise edges such that the change of the distances of the pairs of nodes is suppressed. Through our experiments, we have confirmed that our algorithm maintains the given distances between nodes in the anonymized graph.