Deakin University
Browse
1/1
2 files

Conditional adjacency anonymity in social graphs under active attacks

journal contribution
posted on 2019-10-01, 00:00 authored by S Mauw, Y Ramírez-Cruz, Rolando Trujillo RasuaRolando Trujillo Rasua
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.

History

Journal

Knowledge and information systems

Volume

61

Issue

1

Pagination

485 - 511

Publisher

Springer

Location

New York, N.Y.

ISSN

0219-1377

eISSN

0219-3116

Language

eng

Publication classification

C Journal article; C1 Refereed article in a scholarly journal

Copyright notice

2018, The Authors