%0 Conference Paper %D 2011 %T Link prediction by de-anonymization: How We Won the Kaggle Social Network Challenge %A Narayanan, A. %A Elaine Shi %A Rubinstein, B.I.P. %K deanonymization %K Flickr social photo sharing Website %K graph theory %K IJCNN 2011 social network challenge %K Kaggle social network challenge %K learning (artificial intelligence) %K machine learning %K realworld link prediction %K Simulated annealing %K simulated annealing-based weighted graph matching algorithm %K social networking (online) %X 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. %P 1825 - 1834 %8 2011 %G eng