The impact of unlinkability on adversarial community detection: effects and countermeasures

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

10 Citations (Scopus)


We consider the threat model of a mobile-adversary drawn from contemporary computer security literature, and explore the dynamics of community detection and hiding in this setting. Using a real-world social network, we examine the extent of network topology information an adversary is required to gather in order to accurately ascertain community membership information. We show that selective surveillance strategies can improve the adversary's efficiency over random wiretapping. We then consider possible privacy preserving defenses; using anonymous communications helps, but not much; however, the use of counter-surveillance techniques can significantly reduce the adversary's ability to learn community membership. Our analysis shows that even when using anonymous communications an adversary placing a selectively chosen 8% of the nodes of this network under surveillance (using key-logger probes) can de-anonymize the community membership of as much as 50% of the network. Uncovering all community information with targeted selection requires probing as much as 75% of the network. Finally, we show that a privacy conscious community can substantially disrupt community detection using only local knowledge even while facing up to the asymmetry of a completely knowledgeable mobile-adversary.

Original languageEnglish
Title of host publicationPrivacy Enhancing Technologies - 10th International Symposium, PETS 2010, Proceedings
Place of PublicationBerlin
Number of pages20
ISBN (Print)3642145264, 9783642145261
Publication statusPublished - 16 Aug 2010
Event10th International Symposium on Privacy Enhancing Technologies, PETS 2010 - Berlin, Germany
Duration: 21 Jul 201023 Jul 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6205 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference10th International Symposium on Privacy Enhancing Technologies, PETS 2010


  • social network
  • betweenness centrality
  • community detection
  • threat model
  • community detection algorithm
  • data privacy
  • electric network topology
  • adversarial community detection
  • anonymous communication
  • surveillance techniques

Fingerprint Dive into the research topics of 'The impact of unlinkability on adversarial community detection: effects and countermeasures'. Together they form a unique fingerprint.

Cite this