Hay, M., D. Jensen, G. Miklau, D. Towsley and P. Weis. (2008). Resisting Structural Re-identification in Anonymized Social Networks . University of Massachusetts Amherst, Technical Report 08-12.

Abstract

We identify privacy risks associated with releasing network data sets and provide an algorithm that mitigates those risks. A network data set consists of entities connected by links representing relations such as friendship, communication, or shared activity. Maintaining privacy when publishing networked data is uniquely challenging because an individual’s network context can be used to identify them even if other identifying information is removed. In this paper, we quantify the privacy risks associated with three classes of attacks on the privacy of individuals in graphs, based on the knowledge used by the adversary. We show that the risks of these attacks vary strongly based on network structure and size. We propose a novel approach to anonymizing network data that models aggregate network structure and then allows samples to be drawn from that model. The approach guarantees anonymity for network entities while preserving the ability to estimate a wide variety of network measures with relatively little bias.

Text

A PDF version of this paper is available.

---

Feedback Fineprint