Fundamental Privacy Limits in Bipartite Networks Under Active Attacks

Mahshad Shariatnasab, Farhad Shirani, Elza Erkip

Research output: Contribution to journalArticlepeer-review


This work considers active deanonymization of bipartite networks. The scenario arises naturally in evaluating privacy in various applications such as social networks, mobility networks, and medical databases. For instance, in active deanonymization of social networks, an anonymous victim is targeted by an attacker (e.g. the victim visits the attacker's website), and the attacker queries her group memberships (e.g. by querying the browser history) to deanonymize her. In this work, the fundamental limits of privacy, in terms of the minimum number of queries necessary for deanonymization, is investigated. A stochastic model is considered, where 1) the bipartite network of group memberships is generated randomly; 2) the attacker has partial prior knowledge of the group memberships; and 3) it receives noisy responses to its real-time queries. The bipartite network is generated based on linear and sublinear preferential attachment, and the stochastic block model. The victim's identity is chosen randomly based on a distribution modeling the users' risk of being the victim (e.g. probability of visiting the website). An attack algorithm is proposed which builds upon techniques from communication with feedback, and its performance, in terms of expected number of queries, is analyzed. Simulation results are provided to verify the theoretical derivations.

Original languageEnglish (US)
Pages (from-to)940-954
Number of pages15
JournalIEEE Journal on Selected Areas in Communications
Issue number3
StatePublished - Mar 1 2022


  • Privacy
  • active attack
  • bipartite graph
  • deanonymization
  • information thresholds
  • social network

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Fundamental Privacy Limits in Bipartite Networks Under Active Attacks'. Together they form a unique fingerprint.

Cite this