Reidentification and k-anonymity: a model for disclosure risk in graphs

DOI10.1007/S00500-012-0850-4MaRDI QIDQ2392556zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Klara Stokes, Vicenç Torra

Publication date 1 August 2013

Published in Soft Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1112.1978

zbMATH Keywords

\(k\)-anonymous graph\(n\)-confusion

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Abstract: In this article we provide a formal framework for reidentification in general. We define n-confusion as a concept for modelling the anonymity of a database table and we prove that n-confusion is a generalization of k- anonymity. After a short survey on the different available definitions of k- anonymity for graphs we provide a new definition for k-anonymous graph, which we consider to be the correct definition. We provide a description of the k-anonymous graphs, both for the regular and the non-regular case. We also introduce the more flexible concept of (k,l)-anonymous graph. Our definition of (k,l)-anonymous graph is meant to replace a previous definition of (k, l)-anonymous graph, which we here prove to have severe weaknesses. Finally we provide a set of algorithms for k-anonymization of graphs.

Recommendations

• k-ANONYMITY: A MODEL FOR PROTECTING PRIVACY
• k-Anonymization with Minimal Loss of Information
• Weak k-Anonymity: A Low-Distortion Model for Protecting Privacy
• \(k\)-anonymous path privacy on social graphs
• Database Theory - ICDT 2005

Cites work

• scientific article; zbMATH DE number 1183717 (Why is no real title available?)
• A data distortion by probability distribution
• ACHIEVING k-ANONYMITY PRIVACY PROTECTION USING GENERALIZATION AND SUPPRESSION
• Differential Privacy
• Distances between fuzzy sets representing grey level images
• The transferable belief model
• k-ANONYMITY: A MODEL FOR PROTECTING PRIVACY

Cited in

(7)

• \(k\)-metric antidimension: a privacy measure for social graphs
• Some basics on privacy techniques, anonymization and their big data challenges
• Improving the characterization of P-stability for applications in network privacy
• A probabilistic perspective on re-identifiability
• Graphic sequences, distances and \(k\)-degree anonymity
• Active Re-identification Attacks on Periodically Released Dynamic Social Graphs
• Privacy preserving and fast decision for novelty detection using support vector data description

Describes a project that uses

Uses Software

• PrivateLR

This page was built for publication: Reidentification and \(k\)-anonymity: a model for disclosure risk in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2392556)