|Arvind Narayanan Department of Computer Science, Stanford University||
Computer Science Division, UC Berkeley;
|Benjamin I. P. Rubinstein Microsoft Research, Silicon Valley|
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.