Optimal de-anonymization in random graphs with community structure

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


Social network connectivity data that is anonymized and publicized for academic or commercial purposes are often vulnerable to de-anonymization attacks from attackers utilizing side information in the form of a second, public or crawled social network. Correlation between the two networks is the key factor allowing this attack scheme to work successfully. In this work, the best attack strategy available to de-anonymization attacker, namely the maximum a posteriori (MAP) estimate of the user identities, is identified for networks with community structure and sufficient conditions for perfect de-anonymization are obtained.

Original languageEnglish (US)
Title of host publication37th IEEE Sarnoff Symposium, Sarnoff 2016
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781509015405
StatePublished - Feb 7 2017
Event37th IEEE Sarnoff Symposium, Sarnoff 2016 - Newark, United States
Duration: Sep 19 2016Sep 21 2016

Publication series

Name37th IEEE Sarnoff Symposium, Sarnoff 2016


Other37th IEEE Sarnoff Symposium, Sarnoff 2016
Country/TerritoryUnited States

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Hardware and Architecture

Cite this