DGA Algorithm

DGA (Directed Graph Anonymization) Algorithm

DGA is an algorithm for k-degree anonymization on directed networks. The first step of the algorithm, the Independent (ki,ko)-degree anonymity and Paired k-degree anonymity are implemented in R, and the second step, the graph modification, is implemented in Java.

It was presented in:

  • J. Casas-Roma, J. Salas, F. D. Malliaros and M. Vazirgiannis. (2018). k-Degree Anonymity on Directed Networks. Knowledge and Information Systems (KAIS), In pressdoi:10.1007/s10115-018-1251-5

Abstract: In this paper, we consider the problem of anonymization on directed networks. Although there are several anonymization methods for networks, most of them have been explicitly designed to work with undirected networks and they can not be applied directly to directed graphs. Moreover, ignoring the direction of the edges causes important information loss on the anonymized networks. Here, we propose two different models to achieve k-degree anonymity on directed networks, and we also present algorithms to fulfill these k-degree anonymity models. Given a network G, we construct a k-degree anonymous network by the minimum number of edge additions. Our algorithms use micro-aggregation and integer linear programming to anonymize the degree sequence, and then they modify the graph structure to meet the k-degree anonymous sequence. We apply our algorithms to several real datasets and demonstrate their efficiency and practical utility.

The code (implemented in R and Java) can be downloaded:

For any trouble or comment, please feel free to contact me.