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

DOI10.1007/S00500-012-0850-4zbMATH Open1270.68233DBLPjournals/soco/StokesT12arXiv1112.1978OpenAlexW2047002475WikidataQ57608812 ScholiaQ57608812MaRDI QIDQ2392556FDOQ2392556

Authors: Klara Stokes, Vicenç Torra 

Publication date: 1 August 2013

Published in: Soft Computing (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

• Differential Privacy
• The transferable belief model
• Title not available (Why is that?)
• k-ANONYMITY: A MODEL FOR PROTECTING PRIVACY
• ACHIEVING k-ANONYMITY PRIVACY PROTECTION USING GENERALIZATION AND SUPPRESSION
• Distances between fuzzy sets representing grey level images
• A data distortion by probability distribution

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

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)