L-opacity: Linkage-aware graph anonymization

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-ident...

Full description

Saved in:
Bibliographic Details
Main Authors: NOBARI, Sadegh, KARRAS, Panagiotis, PANG, Hwee Hwa, BRESSAN, Stephane
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2014
Subjects:
Online Access:https://ink.library.smu.edu.sg/sis_research/3662
https://ink.library.smu.edu.sg/context/sis_research/article/4664/viewcontent/L_Opacity_2014_EDBT.pdf
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
id sg-smu-ink.sis_research-4664
record_format dspace
spelling sg-smu-ink.sis_research-46642017-07-11T15:09:35Z L-opacity: Linkage-aware graph anonymization NOBARI, Sadegh KARRAS, Panagiotis PANG, Hwee Hwa BRESSAN, Stephane 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. 2014-03-01T08:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/3662 info:doi/10.5441/002/edbt.2014.52 https://ink.library.smu.edu.sg/context/sis_research/article/4664/viewcontent/L_Opacity_2014_EDBT.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Algorithms Experimentation Theory Databases and Information Systems Theory and Algorithms
institution Singapore Management University
building SMU Libraries
continent Asia
country Singapore
Singapore
content_provider SMU Libraries
collection InK@SMU
language English
topic Algorithms
Experimentation
Theory
Databases and Information Systems
Theory and Algorithms
spellingShingle Algorithms
Experimentation
Theory
Databases and Information Systems
Theory and Algorithms
NOBARI, Sadegh
KARRAS, Panagiotis
PANG, Hwee Hwa
BRESSAN, Stephane
L-opacity: Linkage-aware graph anonymization
description 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.
format text
author NOBARI, Sadegh
KARRAS, Panagiotis
PANG, Hwee Hwa
BRESSAN, Stephane
author_facet NOBARI, Sadegh
KARRAS, Panagiotis
PANG, Hwee Hwa
BRESSAN, Stephane
author_sort NOBARI, Sadegh
title L-opacity: Linkage-aware graph anonymization
title_short L-opacity: Linkage-aware graph anonymization
title_full L-opacity: Linkage-aware graph anonymization
title_fullStr L-opacity: Linkage-aware graph anonymization
title_full_unstemmed L-opacity: Linkage-aware graph anonymization
title_sort l-opacity: linkage-aware graph anonymization
publisher Institutional Knowledge at Singapore Management University
publishDate 2014
url https://ink.library.smu.edu.sg/sis_research/3662
https://ink.library.smu.edu.sg/context/sis_research/article/4664/viewcontent/L_Opacity_2014_EDBT.pdf
_version_ 1770573473461043200