General Graph Data De-Anonymization
Abstract
When people utilize social applications and services, their privacy suffers a potential serious threat. In this article, we present a novel, robust, and effective de-anonymization attack to mobility trace data and social data. First, we design a Unified Similarity (US) measurement, which takes account of local and global structural characteristics of data, information obtained from auxiliary data, and knowledge inherited from ongoing de-anonymization results. By analyzing the measurement on real datasets, we find that some data can potentially be de-anonymized accurately and the other can be de-anonymized in a coarse granularity. Utilizing this property, we present a US-based De-Anonymization (DA) framework, which iteratively de-anonymizes data with accuracy guarantee. Then, to de-anonymize large-scale data without knowledge of the overlap size between the anonymized data and the auxiliary data, we generalize DA to an Adaptive De-Anonymization (ADA) framework. By smartly working on two core matching subgraphs , ADA achieves high de-anonymization accuracy and reduces computational overhead. Finally, we examine the presented de-anonymization attack on three well-known mobility traces: St Andrews, Infocom06, and Smallblue, and three social datasets: ArnetMiner, Google+, and Facebook. The experimental results demonstrate that the presented de-anonymization framework is very effective and robust to noise.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Apr 21, 2016
- Source ID
- 10.1145/2894760
Entities
People
- Jing Selena He
- Mudhakar Srivatsa
- Raheem Beyah
- Shouling Ji
- Weiqing Li
Organizations
- Federal Government of the United States
- Georgia Tech
- Government of the United Kingdom
- International Business Machines Corporation (Armonk, NY)
- Kennesaw State University
- Ministry of Defence of the United Kingdom
- United States Army Research Laboratory