Link Prediction by De-anonymization: How We Won the Kaggle Social Network Challenge
arXiv:1102.4374
Abstract
This paper describes the winning entry to the IJCNN 2011 Social Network Challenge run by Kaggle.com. The goal of the contest was to promote research on real-world link prediction, and the dataset was a graph obtained by crawling the popular Flickr social photo sharing website, with user identities scrubbed. By de-anonymizing much of the competition test set using our own Flickr crawl, we were able to effectively game the competition. Our attack represents a new application of de-anonymization to gaming machine learning contests, suggesting changes in how future competitions should be run. We introduce a new simulated annealing-based weighted graph matching algorithm for the seeding step of de-anonymization. We also show how to combine de-anonymization with link prediction---the latter is required to achieve good performance on the portion of the test set not de-anonymized---for example by training the predictor on the de-anonymized portion of the test set, and combining probabilistic predictions from de-anonymization and link prediction.
11 pages, 13 figures; submitted to IJCNN'2011
References in corpus (1)
Cited by in corpus (12)
- Evaluating Link Prediction Methods
- SiGMa: Simple Greedy Matching for Aligning Large Knowledge Bases
- Privacy in Social Media: Identification, Mitigation and Applications
- An Efficient and Robust Social Network De-anonymization Attack
- IGLOO: Integrating global and local biological network alignment
- Graphlets versus node2vec and struc2vec in the task of network alignment
- Everything About You: A Multimodal Approach towards Friendship Inference in Online Social Networks
- From homogeneous to heterogeneous network alignment via colored graphlets
- MAGNA: Maximizing Accuracy in Global Network Alignment
- Simultaneous Optimization of Both Node and Edge Conservation in Network Alignment via WAVE
- An operational architecture for privacy-by-design in public service applications
- Ethical Considerations when Employing Fake Identities in OSN for Research