Anonymising social graphs in the presence of active attackers

The publication of social network graphs enables researchers to understand and investigate human behaviour. However, when such analyses can target single individuals rather than society as a whole, it is clear that privacy becomes a serious concern. This article addresses the challenge of publishing social graphs with proven privacy guarantees. In our adversarial model we consider an active attacker, who has the capability of altering the structure of the social graph before publication by creating new user profiles and establishing relations between them and the targeted network users. We aim to protect graphs satisfying (1, 1)-anonymity, the privacy property that char-acterises the weakest graphs in terms of resistance to active attacks. To that end, we introduce a class of perturbation methods based on edge additions that transform a (1, 1)-anonymous graph into a graph satisfying (k, ℓ)-anonymity for some k > 1 or some ℓ > 1. We prove the correctness of our approach and give a tight upper bound on the number of necessary edge additions. Experimental results, obtained on real-life graphs and a large collection of randomly generated graphs, show that our methods effectively prevent attacks from active adversaries with the capability of adding one node to the network, and additionally provide some level of protection against more capable attackers. We also conducted experiments on real-life social graphs which show that the outputs of state-of-the-art community detection algorithms on the anonymised graphs is similar to those obtained on the original graphs.