De-anonymizing Social Networks
arXiv:0903.3276 · doi:10.1109/SP.2009.22
Abstract
Operators of online social networks are increasingly sharing potentially sensitive information about users and their relationships with advertisers, application developers, and data-mining researchers. Privacy is typically protected by anonymization, i.e., removing names, addresses, etc. We present a framework for analyzing privacy and anonymity in social networks and develop a new re-identification algorithm targeting anonymized social-network graphs. To demonstrate its effectiveness on real-world networks, we show that a third of the users who can be verified to have accounts on both Twitter, a popular microblogging service, and Flickr, an online photo-sharing site, can be re-identified in the anonymous Twitter graph with only a 12% error rate. Our de-anonymization algorithm is based purely on the network topology, does not require creation of a large number of dummy "sybil" nodes, is robust to noise and all existing defenses, and works even when the overlap between the target network and the adversary's auxiliary information is small.
Published in the 30th IEEE Symposium on Security and Privacy, 2009. The definitive version is available at: http://www.cs.utexas.edu/~shmat/shmat_oak09.pdf Frequently Asked Questions are answered at: http://www.cs.utexas.edu/~shmat/socialnetworks-faq.html
References in corpus (2)
Cited by in corpus (112)
- Knowledge Graphs
- Technical Privacy Metrics: a Systematic Survey
- Differential Privacy: An Economic Method for Choosing Epsilon
- Hiding Individuals and Communities in a Social Network
- Preserving Link Privacy in Social Network Based Systems
- Systematizing Decentralization and Privacy: Lessons from 15 Years of Research and Deployments
- The CSO Classifier: Ontology-Driven Detection of Research Topics in Scholarly Articles
- Towards matching user mobility traces in large-scale datasets
- Inference using noisy degrees: Differentially private -model and synthetic graphs
- Safety Challenges and Solutions in Mobile Social Networks
- An Analysis of Anonymity in the Bitcoin System
- Exact alignment recovery for correlated Erdős-Rényi graphs
- X-Vine: Secure and Pseudonymous Routing Using Social Networks
- Quantifying the Re-identification Risk of Event Logs for Process Mining
- Link Prediction by De-anonymization: How We Won the Kaggle Social Network Challenge
- Evaluating the Strength of Genomic Privacy Metrics
- Privacy in Social Media: Identification, Mitigation and Applications
- Faceless Person Recognition; Privacy Implications in Social Media
- Adversarial Image Perturbation for Privacy Protection -- A Game Theory Perspective
- Efficient random graph matching via degree profiles
- Web Tracking: Mechanisms, Implications, and Defenses
- Finding Nemo: Searching and Resolving Identities of Users Across Online Social Networks
- Spectral Graph Matching and Regularized Quadratic Relaxations I: The Gaussian Model
- A Random Matrix Approach to Differential Privacy and Structure Preserved Social Network Graph Publishing
- An Efficient and Robust Social Network De-anonymization Attack
- De-anonymization of Social Networks with Communities: When Quantifications Meet Algorithms
- Towards Privacy-Preserving Visual Recognition via Adversarial Training: A Pilot Study
- Testing network correlation efficiently via counting trees
- walk2friends: Inferring Social Links from Mobility Profiles
- Rethinking -anonymity in social graphs: -adjacency anonymity and -(adjacency) anonymous transformations
- Using Metrics Suites to Improve the Measurement of Privacy in Graphs
- Applications of Differential Privacy in Social Network Analysis: A Survey
- Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communities
- Literature Survey on Interplay of Topics, Information Diffusion and Connections on Social Networks
- Identity and Personhood in Digital Democracy: Evaluating Inclusion, Equality, Security, and Privacy in Pseudonym Parties and Other Proofs of Personhood
- Social Networks Research Aspects: A Vast and Fast Survey Focused on the Issue of Privacy in Social Network Sites
- LOGAN: Membership Inference Attacks Against Generative Models
- VOUTE-Virtual Overlays Using Tree Embeddings
- Testing correlation of unlabeled random graphs
- Plausible Deniability for Privacy-Preserving Data Synthesis
- Sharp threshold for alignment of graph databases with Gaussian weights
- Stop the Open Data Bus, We Want to Get Off
- Robust active attacks on social graphs
- Preserving differential privacy under finite-precision semantics
- Social Media and User Privacy
- Synthetic Data -- Anonymisation Groundhog Day
- Graph Matching with Partially-Correct Seeds
- Secure Deep Graph Generation with Link Differential Privacy
- MPGM: Scalable and Accurate Multiple Network Alignment
- Multi-level Graph Convolutional Networks for Cross-platform Anchor Link Prediction
- Large-Scale Parallel Matching of Social Network Profiles
- Network Recovery from Unlabeled Noisy Samples
- Diversity, Topology, and the Risk of Node Re-identification in Labeled Social Graphs
- Directed Networks with a Differentially Private Bi-degree Sequence
- SocialSpy: Browsing (Supposedly) Hidden Information in Online Social Networks
- Profile Matching Across Unstructured Online Social Networks: Threats and Countermeasures
- De-anonymizing scale-free social networks by percolation graph matching
- LinkMirage: How to Anonymize Links in Dynamic Social Systems
- Multi-layered Social Networks
- Injecting Uncertainty in Graphs for Identity Obfuscation
- Significance of Side Information in the Graph Matching Problem
- Social Network Integration: Towards Constructing the Social Graph
- A survey of results on mobile phone datasets analysis
- Comparing Temporal Graphs Using Dynamic Time Warping
- Adversarial Attacks and Defenses for Social Network Text Processing Applications: Techniques, Challenges and Future Research Directions
- Bitcoin and Blockchain: Security and Privacy
- On the Benefits of Sampling in Privacy Preserving Statistical Analysis on Distributed Databases
- Rangzen: Anonymously Getting the Word Out in a Blackout
- SPECTRE: Seedless Network Alignment via Spectral Centralities
- Interlayer link prediction in multiplex social networks: an iterative degree penalty algorithm
- Everything About You: A Multimodal Approach towards Friendship Inference in Online Social Networks
- The Atlas for the Aspiring Network Scientist
- Social Network De-anonymization: More Adversarial Knowledge, More Users Re-Identified?
- On the Privacy of dK-Random Graphs
- Interlayer Link Prediction in Multiplex Social Networks Based on Multiple Types of Consistency between Embedding Vectors
- Active Re-identification Attacks on Periodically Released Dynamic Social Graphs
- Towards Plausible Graph Anonymization
- An efficient reconciliation algorithm for social networks
- MPC meets SNA: A Privacy Preserving Analysis of Distributed Sensitive Social Networks
- De-anonymizing Social Networks with Overlapping Community Structure
- On the Computational Complexities of Three Privacy Measures for Large Networks Under Active Attack
- Random Graph Matching with Improved Noise Robustness
- Graph matching beyond perfectly-overlapping Erdős--Rényi random graphs
- A Record Linkage Model Incorporating Relational Data
- Transforming Graph Representations for Statistical Relational Learning
- Attributed Graph Alignment
- Graph Matching via convex relaxation to the simplex
- Local symmetry in random graphs
- Faster algorithms for the alignment of sparse correlated Erdös-Rényi random graphs
- Matching Entities Across Online Social Networks
- From Closed-world Enforcement to Open-world Assessment of Privacy
- An operational architecture for privacy-by-design in public service applications
- Private Graph Data Release: A Survey
- Privacy-Preserving Social Network with Multigrained and Multilevel Access Control
- An Empirical Study on Android for Saving Non-shared Data on Public Storage
- k-Metric Antidimension: a Privacy Measure for Social Graphs
- On the Reliability of Profile Matching Across Large Online Social Networks
- Efficient and High-Quality Seeded Graph Matching: Employing High Order Structural Information
- Nonadaptive Mastermind Algorithms for String and Vector Databases, with Case Studies
- Temporal Activity Path Based Character Correction in Social Networks
- Seeded graph matching for the correlated Gaussian Wigner model via the projected power method
- SoK: Practical Aspects of Releasing Differentially Private Graphs
- Efficient Quantification of Profile Matching Risk in Social Networks
- RLINK: Deep Reinforcement Learning for User Identity Linkage
- Privacy-Related Consequences of Turkish Citizen Database Leak
- De-Health: All Your Online Health Information Are Belong to Us
- An Abstract View on the De-anonymization Process
- Impact of Clustering on the Performance of Network De-anonymization
- Discussions of the paper "Sparse graphs using exchangeable random measures" by F. Caron and E. B. Fox
- Linking Sequences of Events with Sparse or No Common Occurrence across Data Sets
- Privacy Protection for Mobile Cloud Data: A Network Coding Approach
- Quantification of De-anonymization Risks in Social Networks