A Maximum Variance Approach for Graph Anonymization

Hiep H. Nguyen 1 Abdessamad Imine 1 Michael Rusinowitch 2
1 CASSIS - Combination of approaches to the security of infinite states systems
FEMTO-ST - Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174), Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
2 CASSIS - Combination of approaches to the security of infinite states systems
FEMTO-ST - Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174), INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : Uncertain graphs, a form of uncertain data, have recently attracted a lot of attention as they can represent inherent uncertainty in collected data. The uncertain graphs pose challenges to conventional data processing techniques and open new research directions. Going in the reserve direction, this paper focuses on the problem of anonymizing a deterministic graph by converting it into an uncertain form. The paper first analyzes drawbacks in a recent uncertainty-based anonymization scheme and then proposes Maximum Variance, a novel approach that provides better tradeoff between privacy and utility. Towards a fair com-parison between the anonymization schemes on graphs, the second con-tribution of this paper is to describe a quantifying framework for graph anonymization by assessing privacy and utility scores of typical schemes in a unified space. The extensive experiments show the effectiveness and efficiency of Maximum Variance on three large real graphs.
Type de document :
Communication dans un congrès
The 7th International Symposium on Foundations & Practice of Security FPS’2014, Nov 2014, Montreal, Canada
Liste complète des métadonnées

Littérature citée [25 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01092442
Contributeur : Hiep H. Nguyen <>
Soumis le : lundi 8 décembre 2014 - 16:46:34
Dernière modification le : vendredi 6 juillet 2018 - 15:06:10
Document(s) archivé(s) le : lundi 9 mars 2015 - 12:17:05

Fichier

uncertain-graph-fps-final.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01092442, version 1

Citation

Hiep H. Nguyen, Abdessamad Imine, Michael Rusinowitch. A Maximum Variance Approach for Graph Anonymization. The 7th International Symposium on Foundations & Practice of Security FPS’2014, Nov 2014, Montreal, Canada. 〈hal-01092442〉

Partager

Métriques

Consultations de la notice

360

Téléchargements de fichiers

439