Network Structure and Privacy: The Re-Identification Risk in Graph Data

In graph data, particularly those representing human connections, the structure of relationships can inadvertently expose individuals to privacy risks. Recent research indicates that even when traditional anonymization techniques are applied, the unique patterns within a user's local network—referred to as their "neighborhood"—can be exploited for re-identification. This talk delves into the complexities of anonymizing graph data, emphasizing that connections themselves serve as distinctive features that can compromise user privacy. This talk examines the relationship between a network's average degree (i.e. the amount of nodes' connections) and the severity of uniquely identify a node in it solely based on the network's structure. We discuss how understanding these risks can inform the design of privacy-aware data collection and anonymization methods, ensuring that the benefits of data sharing are balanced with the imperative to protect individual privacy.

Authors: Daniele Romanini and Sune Lehmann, Technical University of Denmark; Mikko Kivelä, Aalto University