Conditional adjacency anonymity in social graphs under active attacks

Mauw, Sjouke, Ramírez-Cruz, Yunior and Trujillo Rasua, Rolando 2018, Conditional adjacency anonymity in social graphs under active attacks, Knowledge and information systems, doi: 10.1007/s10115-018-1283-x.

Attached Files
Name Description MIMEType Size Downloads

Title Conditional adjacency anonymity in social graphs under active attacks
Author(s) Mauw, Sjouke
Ramírez-Cruz, Yunior
Trujillo Rasua, RolandoORCID iD for Trujillo Rasua, Rolando
Journal name Knowledge and information systems
Total pages 27
Publisher Springer
Place of publication New York, N.Y.
Publication date 2018-12-27
ISSN 0219-1377
Summary Social network data is typically made available in a graph format, where users and their relations are represented by vertices and edges, respectively. In doing so, social graphs need to be anonymised to resist various privacy attacks. Among these, the so-called active attacks, where an adversary has the ability to enrol sybil accounts in the social network, have proven difficult to counteract. In this article, we provide an anonymisation technique that successfully thwarts active attacks while causing low structural perturbation. We achieve this goal by introducing (k, Γ G,ℓ) -adjacency anonymity: a privacy property based on (k, ℓ) -anonymity that alleviates the computational burden suffered by anonymisation algorithms based on (k, ℓ) -anonymity and relaxes some of its assumptions on the adversary capabilities. We show that the proposed method is efficient and establish tight bounds on the number of modifications that it performs on the original graph. Experimental results on real-life and randomly generated graphs show that when compared to methods based on (k, ℓ) -anonymity, the new method continues to provide protection from equally capable active attackers while introducing a much smaller number of changes in the graph structure.
Notes In Press
Language eng
DOI 10.1007/s10115-018-1283-x
Indigenous content off
Field of Research 0801 Artificial Intelligence And Image Processing
HERDC Research category C1 Refereed article in a scholarly journal
ERA Research output type C Journal article
Copyright notice ©2018, The Authors
Persistent URL

Connect to link resolver
Unless expressly stated otherwise, the copyright for items in DRO is owned by the author, with all rights reserved.

Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 1 times in TR Web of Science
Scopus Citation Count Cited 2 times in Scopus
Google Scholar Search Google Scholar
Access Statistics: 84 Abstract Views, 2 File Downloads  -  Detailed Statistics
Created: Thu, 24 Jan 2019, 15:13:59 EST

Every reasonable effort has been made to ensure that permission has been obtained for items included in DRO. If you believe that your rights have been infringed by this repository, please contact