A Constraint Programming Approach to Optimal Network Anonymization
A. Ionita (TU Delft - Electrical Engineering, Mathematics and Computer Science)
A.L.D. Latour – Mentor (TU Delft - Algorithmics)
Carolin 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
In the age of the internet, social networks are being used to study different phenomena, such as segre- gation, disease spread, or even peer influence. This introduces the need to protect the privacy of the in- dividuals that are part of these networks, a problem known in the field of network science by the name of network anonymization. This involves altering the initial network using different methods such as adding, removing, or altering edges, in order to pre- vent attackers from identifying specific individuals. One aspect that has been studied is the data util- ity of the anonymized network: if we alter the ini- tial network too much, its usability for studies is lowered. Thus, in this work, we propose a con- straint programming approach that minimizes the anonymization cost, in turn maximizing the data utility of the final network. We introduce a new iso- morphic_neighborhoods constraint and show that, for small(n < 20) or highly dense graphs, we can guarantee the maximum data utility, by adding the fewest number of edges that guarantee anonymity.