Cluster-Based Anonymization of Directed Graphs

Social network providers anonymize graphs storing users' relationships to protect users from being re-identified. Despite the fact that most of the relationships are directed (e.g., follows), few works (e.g., the Paired k-degree [1] and K-In&Out-Degree Anonymity [2]) have been designed to work with directed graphs. In this paper, we show that given a graph, DGA [1] and DSNDG-KIODA [2] are not always able to generate its anonymized version. We overcome this limitation by presenting the Cluster-based Directed Graph Anonymization Algorithm (CDGA) and prove that, by choosing the appropriate parameters, CDGA can generate an anonymized graph satisfying both the Paired k-degree [1] and K-In&Out-Degree Anonymity [2]. Also, we present the Out- and In-Degree Information Loss Metric to minimize the number of changes made to anonymize the graph. We conduct extensive experiments on three real-life data sets to evaluate the effectiveness of CDGA and compare the quality of the graphs anonymized by CDGA, DGA, and DSNDG-KIODA. The experimental results show that we can generate anonymized graphs, by modifying less than 0.007% of edges in the original graph.