Skip to Main content Skip to Navigation
New interface
Conference papers

A Maximum Variance Approach for Graph Anonymization

Huu Hiep Nguyen 1 Abdessamad Imine 1 Michael 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 : 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [25 references]  Display  Hide  Download
Contributor : Hiep H. Nguyen Connect in order to contact the contributor
Submitted on : Monday, December 8, 2014 - 4:46:34 PM
Last modification on : Friday, January 21, 2022 - 3:09:05 AM
Long-term archiving on: : Monday, March 9, 2015 - 12:17:05 PM


Files produced by the author(s)


  • HAL Id : hal-01092442, version 1


Huu Hiep 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⟩



Record views


Files downloads