Seed-Based De-Anonymizability Quantification of Social Networks

Shouling Ji, Weiqing Li, Neil Zhenqiang Gong, Prateek Mittal, Raheem Beyah

Research output: Contribution to journalArticlepeer-review

26 Scopus citations


In this paper, we implement the first comprehensive quantification of the perfect de-anonymizability and partial de-anonymizability of real-world social networks with seed information under general scenarios, which provides the theoretical foundation for the existing structure-based de-anonymization attacks and closes the gap between de-anonymization practice and theory. Based on our quantification, we conduct a large-scale evaluation of the de-anonymizability of 24 real-world social networks by quantitatively showing the conditions for perfectly and partially de-anonymizing a social network, how de-anonymizable a social network is, and how many users of a social network can be successfully de-anonymized. Furthermore, we show that both theoretically and experimentally, the overall structural information-based de-anonymization attack can be more powerful than the seed-based de-anonymization attack, and even without any seed information, a social network can be perfectly or partially de-anonymized. Finally, we discuss the implications of this paper. Our findings are expected to shed on research questions in the areas of structural data anonymization and de-anonymization and to help data owners evaluate their structural data vulnerability before data sharing and publishing.

Original languageEnglish (US)
Article number7405301
Pages (from-to)1398-1411
Number of pages14
JournalIEEE Transactions on Information Forensics and Security
Issue number7
StatePublished - Jul 2016

All Science Journal Classification (ASJC) codes

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


  • De-anonymization
  • evaluation
  • social networks


Dive into the research topics of 'Seed-Based De-Anonymizability Quantification of Social Networks'. Together they form a unique fingerprint.

Cite this