Study Data from Open University Provide New Insights into Information Technology (Identity obfuscation in graphs through the information theoretic lens)
By a News Reporter-Staff News Editor at Information Technology Newsweekly -- Current study results on Information Technology have been published. According to news reporting originating in Raanana, Israel, by VerticalNews journalists, research stated, "Analyzing the structure of social networks is of interest in a wide range of disciplines. Unfortunately, sharing social-network datasets is often restrained by privacy considerations."
The news reporters obtained a quote from the research from Open University, "One way to address the privacy concern is to anonymize the data before publishing. Randomly adding or deleting edges from the social graph is one of the anonymization approaches that have been proposed in the literature. 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 cannot achieve meaningful levels of anonymity without deteriorating the graph properties. We offer a new information-theoretic perspective on the question of anonymizing a social network by means of random edge additions and deletions. 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 that was based on a posteriori belief probabilities. We also prove that the anonymity level as 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 properties of the original graph. As the methods we study add and remove edges, it is natural to ask whether an adversary might use the disclosed perturbed graph structure to reconstruct, even partially, the original graph. We thus study the resilience of obfuscation by random sparsification to adversarial attacks that are based on link prediction. Given a general link prediction method, with a predefined level of prediction accuracy, we show how to quantify the level of anonymity that is guaranteed by the obfuscation. We empirically prove that even for very accurate link prediction methods, the level of anonymity guaranteed remains very close to the one before the attack."
According to the news reporters, the research concluded: "Finally, we show how the randomization method may be applied in a distributed setting, where the network data is distributed among several non-trusting sites, and explain why randomization is far more suitable for such settings than other existing approaches."
For more information on this research see: Identity obfuscation in graphs through the information theoretic lens. Information Sciences, 2014;275():232-256. Information Sciences can be contacted at: Elsevier Science Inc, 360 Park Ave South, New York, NY 10010-1710, USA. (Elsevier - www.elsevier.com; Information Sciences - www.elsevier.com/wps/product/cws_home/505730)
Our news correspondents report that additional information may be obtained by contacting F. Bonchi, Open University, Dept. of Math & Comp Sci, Raanana, Israel. Additional authors for this research include A. Gionis and T. Tassa.
Keywords for this news article include: Asia, Israel, Raanana, Information Technology
Our reports deliver fact-based news of research and discoveries from around the world. Copyright 2014, NewsRx LLC