  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 i) the bipartite network of group
memberships is generated randomly, ii) the attacker has partial prior knowledge
of the group memberships, and iii) 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.
