Publication Type
Conference Proceeding Article
Version
publishedVersion
Publication Date
3-2014
Abstract
The wealth of information contained in online social networks has created a demand for the publication of such data as graphs. Yet, publication, even after identities have been removed, poses a privacy threat. Past research has suggested ways to publish graph data in a way that prevents the re-identification of nodes. However, even when identities are effectively hidden, an adversary may still be able to infer linkage between individuals with sufficiently high confidence. In this paper, we focus on the privacy threat arising from such link disclosure. We suggest L-opacity, a sufficiently strong privacy model that aims to control an adversary’s confidence on short multiedge linkages among nodes. We propose an algorithm with two variant heuristics, featuring a sophisticated look-ahead mechanism, which achieves the desired privacy guarantee after a few graph modifications. We empirically evaluate the performance of our algorithm, measuring the alteration inflicted on graphs and various utility metrics quantifying spectral and structural graph properties, while we also compare them to a recently proposed, albeit limited in generality of scope, alternative. Thereby, we demonstrate that our algorithms are more general, effective, and efficient than the competing technique, while our heuristic that preserves the number of edges in the graph constant fares better overall than one that reduces it.
Keywords
Algorithms, Experimentation, Theory
Discipline
Databases and Information Systems | Theory and Algorithms
Publication
Advances in Database Technology: EDBT 2014, 17th International Conference on Extending Database Technology, Athens, Greece, March 24-28, Proceedings
First Page
583
Last Page
594
ISBN
9783893180653
Identifier
10.5441/002/edbt.2014.52
Publisher
OpenProceedings
City or Country
Konstanz
Embargo Period
7-11-2017
Citation
NOBARI, Sadegh; KARRAS, Panagiotis; PANG, Hwee Hwa; and BRESSAN, Stephane.
L-opacity: Linkage-aware graph anonymization. (2014). Advances in Database Technology: EDBT 2014, 17th International Conference on Extending Database Technology, Athens, Greece, March 24-28, Proceedings. 583-594.
Available at: https://ink.library.smu.edu.sg/sis_research/3662
Copyright Owner and License
Authors
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
http://doi.org/10.5441/002/edbt.2014.52