Towards Plausible Graph Anonymization
Yang Zhang, Mathias Humbert, Bartlomiej Surma, Praveen Manoharan, Jilles Vreeken, Michael Backes
Abstract
Social graphs derived from online social interactions contain a wealth of information that is nowadays extensively used by both industry and academia. However, as social graphs contain sensitive information, they need to be properly anonymized before release. Most of the existing graph anonymization mechanisms rely on the perturbation of the original graph's edge set. In this paper, we identify a fundamental weakness of these mechanisms: They neglect the strong structural proximity between friends in social graphs, thus add implausible fake edges for anonymization.
Topics & Concepts
Computer scienceGraphTheoretical computer sciencePrivacy-Preserving Technologies in DataPrivacy, Security, and Data ProtectionInternet Traffic Analysis and Secure E-voting