20 20

Transactions on
Data Privacy
Foundations and Technologies


Articles in Press

Accepted articles here

Latest Issues

Year 2018

Volume 11 Issue 3
Volume 11 Issue 2
Volume 11 Issue 1

Year 2017

Volume 10 Issue 3
Volume 10 Issue 2
Volume 10 Issue 1

Year 2016

Volume 9 Issue 3
Volume 9 Issue 2
Volume 9 Issue 1

Year 2015

Volume 8 Issue 3
Volume 8 Issue 2
Volume 8 Issue 1

Year 2014

Volume 7 Issue 3
Volume 7 Issue 2
Volume 7 Issue 1

Year 2013

Volume 6 Issue 3
Volume 6 Issue 2
Volume 6 Issue 1

Year 2012

Volume 5 Issue 3
Volume 5 Issue 2
Volume 5 Issue 1

Year 2011

Volume 4 Issue 3
Volume 4 Issue 2
Volume 4 Issue 1

Year 2010

Volume 3 Issue 3
Volume 3 Issue 2
Volume 3 Issue 1

Year 2009

Volume 2 Issue 3
Volume 2 Issue 2
Volume 2 Issue 1

Year 2008

Volume 1 Issue 3
Volume 1 Issue 2
Volume 1 Issue 1

Volume 11 Issue 2

Anonymising social graphs in the presence of active attackers

Sjouke Mauw(a),(b), Yunior Ramírez-Cruz(b),(*), Rolando Trujillo-Rasua(b),(c)

Transactions on Data Privacy 11:2 (2018) 169 - 198

Abstract, PDF

(a) CSC, University of Luxembourg, 6 av. de la Fonte, L-4364 Esch-sur-Alzette, Luxembourg.

(b) SnT, University of Luxembourg, 6 av. de la Fonte, L-4364 Esch-sur-Alzette, Luxembourg.

(c) School of Information Technology, Deakin University, 221 Burwood Hwy., Burwood VIC 3125, Australia.

e-mail:sjouke.mauw @uni.lu; yunior.ramirez @uni.lu; rolando.trujillo @deakin.edu.au


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 characterises 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,l)-anonymity for some k ≥ 1 or some l ≥ 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.

* Corresponding author.

Follow us


ISSN: 1888-5063; ISSN (Digital): 2013-1631; D.L.:B-11873-2008; Web Site: http://www.tdp.cat/
Contact: Transactions on Data Privacy; Vicenç Torra; U. of Skövde; PO Box 408; 54128 Skövde; (Sweden); e-mail:tdp@tdp.cat
Note: TDP's web site does not use cookies. TDP does not keep information neither on IP addresses nor browsers. For the privacy policy access here.


Vicenç Torra, Last modified: 05 : 40 August 26 2018.