Measuring Anonymity in Complex Networks

Poster presentation by Rachel de Jong at IC2S2 conference

Authors: Rachel de Jong; Mark van der Loo; Frank Takes

Complex networks are often used to describe the interactions between individuals or organizations within social or economic systems. In order to comply with regulations regarding privacy and data protection, such data is frequently anonymized by leaving out personal identifiers of the nodes. However, in such cases (properties of) a seemingly anonymized individual may still be re-identified based on its structural position in the network [1].

This is particularly relevant for National Statistical Institutes (NSIs) that are applying network science to population scale social network data [2]. When releasing data for research purposes, NSIs rely on statistical disclosure control (SDC) techniques for data protection [3]. A central concept in this field is anonymity: the number of equivalent data points in an anonymized data set. Anonymity is an essential component in assessing the risk of disclosure.

This work presents a method for measuring the disclosure probability of nodes in networks, that takes as a parameter the amount of information an adversary has about a node’s surrounding structure. We also provide an in-depth analysis of node anonymity in three well-known complex network models. The proposed j-anonymity distributions can be used to measure disclosure probabilities, which in turn can be used to assess disclosure risk. Numerical experiments reveal that many nodes are de-anonymized when their neighbourhood of radius 2 is known.