Identity obfuscation in graphs through the information theoretic lens

Francesco Bonchi*, Aristides Gionis, Tamir Tassa

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

38 Citations (Scopus)


Analyzing the structure of social networks is of interest in a wide range of disciplines, but such activity is limited by the fact that these data represent sensitive information and can not be published in their raw form. One of the approaches to sanitize network data is to randomly add or remove edges from the graph. Recent studies have quantified the level of anonymity that is obtained by random perturbation by means of a-posteriori belief probabilities and, by conducting experiments on small datasets, arrived at the conclusion that random perturbation can not achieve meaningful levels of anonymity without deteriorating the graph features. We offer a new information-theoretic perspective on this issue. We make an essential distinction between image and preimage anonymity and propose a more accurate quantification, based on entropy, of the anonymity level that is provided by the perturbed network. We explain why the entropy-based quantification, which is global, is more adequate than the previously used local quantification based on a-posteriori belief. We also prove that the anonymity level quantified by means of entropy is always greater than or equal to the one based on a-posteriori belief probabilities. In addition, we introduce and explore the method of random sparsification, which randomly removes edges, without adding new ones. Extensive experimentation on several very large datasets shows that randomization techniques for identity obfuscation are back in the game, as they may achieve meaningful levels of anonymity while still preserving features of the original graph.

Original languageEnglish
Title of host publication2011 IEEE 27th International Conference on Data Engineering
Number of pages12
Publication statusPublished - 2011
MoE publication typeA4 Article in a conference publication
EventInternational Conference on Data Engineering - Hannover, Germany
Duration: 11 Apr 201116 Apr 2011
Conference number: 27

Publication series

NameInternational Conference on Data Engineering
ISSN (Print)2375-0286
ISSN (Electronic)1084-4627


ConferenceInternational Conference on Data Engineering
Abbreviated titleICDE
Internet address


Dive into the research topics of 'Identity obfuscation in graphs through the information theoretic lens'. Together they form a unique fingerprint.

Cite this