Measuring Structural Anonymity in Complex Networks

Master thesis presentation by Rachel de Jong

When sharing sensitive data, it should be made sure that entities represented in it are sufficiently anonymous in order to avoid a possible breach of privacy. In the field of statistical disclosure control, this concept is well studied. However, thus far the majority of work in this field focuses on microdata and (aggregated) tabular data. In this work, we discuss a new measure for anonymity in networks: d-k-anonymity. It improves upon existing measures (which are in most cases too weak, too strict, or not able to account for triangles) by being parametrized in strictness and taking into account all information in the d-neighbourhood of a vertex. This enables the user to select the right level of anonymity based on how much a possible attacker knows. We present an algorithm that can efficiently measure the anonymity and apply it to three well known-graph models with up to 10,000 vertices, as well as a real-world network; the full family network of the Netherlands, consisting of over 15 million vertices. In our experiments, we find that for graph models most anonymity is lost when measuring 2-k-anonymity, and vertices quickly all become unique as the edge density increases. For the family network, over 2.7 million vertices have an anonymity of 1 when measuring 5-k-anonymity, implying that they are uniquely identifiable when their exact position in their 5-neighbourhood is known.

Supervisors: Frank Takes and Mark van der Loo (CBS)

If you wish to join this presentation, please send an email to popnet@uva.nl.