Preserving Privacy in Social Networks: A Structure-Aware Approach
Authors:
- Xiaoyun HeXHXiaoyun He
- Jaideep VaidyaJVJaideep Vaidya
- Basit ShafiqBSBasit Shafiq
- Nabil AdamNANabil Adam
- Vijay AtluriVAVijay Atluri
- 1 September 2009
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 1, 647-654
Abstract
Graph structured data can be ubiquitously found in the real world. For example, social networks can easily be represented as graphs where the graph connotes the complex sets of relationships between members of social systems. While their analysis could be beneficial in many aspects, publishing certain types of social networks raises significant privacy concerns. This brings the problem of graph anonymization into sharp focus. Unlike relational data, the true information in graph structured data is encoded within the structure and graph properties. Motivated by this, we propose a structure aware anonymization approach that maximally preserves the structure of the original network as well as its structural properties while anonymizing it. Instead of anonymizing each node one by one independently, our approach treats each partitioned substructural component of the network as one single unit to be anonymized. This maximizes utility while enabling anonymization. We apply our method to both synthetic and real datasets and demonstrate its effectiveness and practical usefulness.Keywords
This publication has 14 references indexed in Scilit:
- Resisting structural re-identification in anonymized social networksProceedings of the VLDB Endowment, 2008
- Towards identity anonymization on graphs2008
- Preserving Privacy in Social Networks Against Neighborhood Attacks2008
- Preserving the Privacy of Sensitive Relationships in Graph Data2008
- Wherefore art thou r3579x?2007
- A Quantitative Comparison of the Subgraph Miners MoFa, gSpan, FFSM, and Gaston2005
- Mixing Patterns and Community Structure in Networks2003
- Generalizing data to provide anonymity when disclosing information (abstract)1998
- A Fast and High Quality Multilevel Scheme for Partitioning Irregular GraphsSIAM Journal on Scientific Computing, 1998
- Hardness of approximating graph transformation problem1994