A Pseudo-Boolean Approach to Graph Anonymisation
E.A. de Groot (TU Delft - Electrical Engineering, Mathematics and Computer Science)
A.L.D. Latour – Mentor (TU Delft - Algorithmics)
C.E. Brandt – Graduation committee member (TU Delft - Software Engineering)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
This work proposes a pseudo-Boolean optimisation model that computes the minimum number of edge deletions needed to fully anonymise a graph, according to the (n,m)-k-anonymity measure. We survey the usability of this model, by comparing it with an unpublished Integer Linear Program (ILP) optimisation model in terms of running time and memory consumption. For both models, we provide a comparison between two different model solvers. We find a noticeable difference in running time and quality of the solution of the different model solvers. The experiments suggest that both running time and memory consumption of solving the pseudo-boolean model are greater than solving the ILP model by a constant factor. This opens up the possibility for the model to be used in tandem with a pseudo-Boolean proof verifier to provide certificates of solution optimality.