@misc{Narayanan2009,
  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.
},
  author = {Narayanan, Arvind and Shmatikov, Vitaly},
  interhash = {ffb21f5ed2b9b879d911d0b68f3d5c07},
  intrahash = {396299d0adaba60baa0f4c2bd28a93b8},
  note = {cite arxiv:0903.3276
Comment: 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},
  title = {De-anonymizing Social Networks},
  url = {http://arxiv.org/abs/0903.3276},
  year = 2009
}

@inproceedings{narayanan2008robust,
  abstract = {We present a new class of statistical de- anonymization attacks against high-dimensional micro-data, such as individual preferences, recommendations, transaction records and so on. Our techniques are robust to perturbation in the data and tolerate some mistakes in the adversary's background knowledge. We apply our de-anonymization methodology to the Netflix Prize dataset, which contains anonymous movie ratings of 500,000 subscribers of Netflix, the world's largest online movie rental service. We demonstrate that an adversary who knows only a little bit about an individual subscriber can easily identify this subscriber's record in the dataset. Using the Internet Movie Database as the source of background knowledge, we successfully identified the Netflix records of known users, uncovering their apparent political preferences and other potentially sensitive information.},
  author = {Narayanan, Arvind and Shmatikov, Vitaly},
  booktitle = {Proc. of the 29th IEEE Symposium on Security and Privacy},
  doi = {10.1109/SP.2008.33},
  interhash = {77c86be6c4bf7fc51b7faecfe85479fe},
  intrahash = {2748ba4684dbe09120aee56c6a0a9de9},
  issn = {1081-6011},
  month = may,
  pages = {111--125},
  publisher = {IEEE Computer Society},
  title = {Robust De-anonymization of Large Sparse Datasets},
  url = {http://www.cs.utexas.edu/~shmat/shmat_oak08netflix.pdf},
  year = 2008
}

@misc{narayanan-2006,
  abstract = { We present a new class of statistical de-anonymization attacks against high-dimensional micro-data, such as individual preferences, recommendations, transaction records and so on. Our techniques are robust to perturbation in the data and tolerate some mistakes in the adversary's background knowledge.},
  author = {Narayanan, Arvind and Shmatikov, Vitaly},
  interhash = {6be42821c2588b6442d6fb8ac7cd8a6e},
  intrahash = {86b686a7fad55fa225123b2f79de87a8},
  title = {How To Break Anonymity of the Netflix Prize Dataset},
  url = {http://www.citebase.org/abstract?id=oai:arXiv.org:cs/0610105},
  year = 2006
}