Contents

• Abstract
• Introduction
• Background
  • Social network challenge dataset
  • Flickr crawl dataset
  
  
• De-anonymization
  • Seed identification
  • Propagation
  • Results
  
  
• Graph Matching via Simulated Annealing
• Link Prediction
  • Use of voting to increase edge coverage
  
  
• Related work
• Discussion
• Conclusions & Open Problems
• Acknowledgments
• Bibliography

Link Prediction by De-anonymization:
How We Won the Kaggle Social Network Challenge

Arvind Narayanan Department of Computer Science, Stanford University

Elaine Shi Computer Science Division, UC Berkeley; PARC

Benjamin I. P. Rubinstein Microsoft Research, Silicon Valley

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.