De-anonymizing social networks

Arvind Narayanan, Vitaly Shmatikov

Research output: Chapter in Book/Report/Conference proceedingConference contribution

930 Scopus citations


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 socialnetwork graphs. To demonstrate its effectiveness on realworld 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 allexisting defenses, and works even when the overlap between the target network and the adversary's auxiliary information is small.

Original languageEnglish (US)
Title of host publication2009 30th IEEE Symposium on Security and Privacy
Number of pages15
StatePublished - 2009
Externally publishedYes
Event2009 30th IEEE Symposium on Security and Privacy - Oakland, CA, United States
Duration: May 17 2009May 20 2009

Publication series

NameProceedings - IEEE Symposium on Security and Privacy
ISSN (Print)1081-6011


Other2009 30th IEEE Symposium on Security and Privacy
Country/TerritoryUnited States
CityOakland, CA

All Science Journal Classification (ASJC) codes

  • Safety, Risk, Reliability and Quality
  • Software
  • Computer Networks and Communications


Dive into the research topics of 'De-anonymizing social networks'. Together they form a unique fingerprint.

Cite this