Anonymizing Social Graphs via Uncertainty Semantics

Hiep H. Nguyen 1 Abdessamad Imine 1 Michaël Rusinowitch 1
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, Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : Rather than anonymizing social graphs by generalizing them to super nodes/edges or adding/removing nodes and edges to satisfy given privacy parameters, recent methods exploit the semantics of uncertain graphs to achieve privacy protection of participating entities and their relationships. These techniques anonymize a deterministic graph by converting it into an uncertain form. In this paper, we propose a general obfuscation model based on uncertain adjacency matrices that keep expected node degrees equal to those in the unanonymized graph. We analyze two recently proposed schemes and their fitting into the model. We also point out disadvantages in each method and present several elegant techniques to fill the gap between them. Finally, to support fair comparisons, we develop a new tradeoff quantifying framework by leveraging the concept of incorrectness. Experiments on large social graphs demonstrate the effectiveness of our schemes.
Type de document :
Communication dans un congrès
ASIACCS 2015 - 10th ACM Symposium on Information, Computer and Communications Security, Apr 2015, Singapour, Singapore
Liste complète des métadonnées

https://hal.inria.fr/hal-01108437
Contributeur : Hiep H. Nguyen <>
Soumis le : jeudi 22 janvier 2015 - 16:47:06
Dernière modification le : jeudi 11 janvier 2018 - 06:24:26

Identifiants

  • HAL Id : hal-01108437, version 1

Citation

Hiep H. Nguyen, Abdessamad Imine, Michaël Rusinowitch. Anonymizing Social Graphs via Uncertainty Semantics. ASIACCS 2015 - 10th ACM Symposium on Information, Computer and Communications Security, Apr 2015, Singapour, Singapore. 〈hal-01108437〉

Partager

Métriques

Consultations de la notice

181