Triangle randomization for social network data anonymization
Presented by Dr. Nacho LOPEZ LORENZO
Type: Oral presentation
Track: Algorithmic Graph Theory
In order to protect privacy of social network participants, graph data should be anonymized prior to its release. Most proposals in the literature aim to achieve $k$-anonymity under different assumptions about the background information of the attacker. In this paper we present a different approach based on randomizing the location of the triangles in the graph. We show that this method preserves the main structural parameters of the graph to a high extent, while providing a high re-identification confusion even in the case of an attacker who is in possession of the whole original graph.