On the Privacy and Utility of Anonymized Social Networks

On the Privacy and Utility of Anonymized Social Networks

Yi Song (Department of Computer Science, School of Computing, National University of Singapore, Singapore), Xuesong Lu (Department of Computer Science, School of Computing, National University of Singapore, Singapore), Sadegh Nobari (Department of Computer Science, School of Computing, National University of Singapore, Singapore), Stéphane Bressan (Department of Computer Science, School of Computing, National University of Singapore, Singapore) and Panagiotis Karras (Department of Management Science & Information Systems, Rutgers Business School, Rutgers University, Newark, NJ, USA)
DOI: 10.4018/jaras.2013040101
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

One is either on Facebook or not. Of course, this assessment is controversial and its rationale arguable. It is nevertheless not far, for many, from the reason behind joining social media and publishing and sharing details of their professional and private lives. Not only the personal details that may be revealed, but also the structure of the networks are sources of invaluable information for any organization wanting to understand and learn about social groups, their dynamics and members. These organizations may or may not be benevolent. It is important to devise, design and evaluate solutions that guarantee some privacy. One approach that reconciles the different stakeholders’ requirement is the publication of a modified graph. The perturbation is hoped to be sufficient to protect members’ privacy while it maintains sufficient utility for analysts wanting to study the social media as a whole. In this paper, the authors try to empirically quantify the inevitable trade-off between utility and privacy. They do so for two state-of-the-art graph anonymization algorithms that protect against most structural attacks, the k-automorphism algorithm and the k-degree anonymity algorithm. The authors measure several metrics for a series of real graphs from various social media before and after their anonymization under various settings.
Article Preview

Backstrom et al. (2007), one of the pioneering works on graph anonymization, point out shortcomings of naive graph anonymization, which replaces identity of individuals by synthetic identifiers. Attackers are able to identify their target from remarkable existing (passive attacks) or created (active attacks) structural local properties of the graph.

To prevent such attacks, various anonymization methods are proposed that further modify the graph in order to hide remarkable structural features.

Liu and Terzi (2008) propose to anonymize graphs by inserting new edges in order to make the degree of each vertex undistinguishable from that of, at least, k-1 other vertices. Attacks based on degree information can be prevented. The graph is said to be k-degree-anonymous after modification. Zhang et al. (2009) propose to swap and delete edges based on degree information in order to prevent re-identification of sensitive edges in simple graph. Ying and Wu (2008) suggest randomized edge addition, deletion and switching to anonymize graph while controlling the effect on graph spectrum.

Zou, Chen, and Ozsu (2009) and Cheng, Fu, and Liu (2010) try and prevent a broader range of structural attacks by proposing a graph modification approach that involve vertices and edges insertion and create homomorphic (thus undistinguishable) components. Similarly, Wu, Xiao, Wang, He, and Wang (2010) propose a k-symmetry model to prevent re-identification via any structural attacks.

Considering labels of vertices in addition to the basic structural information, Zhou and Pei (2008) propose to extract the neighborhoods of all vertices, group vertices and anonymize the neighborhoods of vertices in the same group by generalizing vertex labels and adding edges.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 8: 2 Issues (2017): Forthcoming, Available for Pre-Order
Volume 7: 2 Issues (2016): 1 Released, 1 Forthcoming
Volume 6: 2 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing