Skip to Main content Skip to Navigation
Conference papers

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 (UMR 6174), 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.
Document type :
Conference papers
Complete list of metadatas
Contributor : Hiep H. Nguyen <>
Submitted on : Thursday, January 22, 2015 - 4:47:06 PM
Last modification on : Wednesday, October 14, 2020 - 4:07:21 AM


  • HAL Id : hal-01108437, version 1


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⟩



Record views