On Anonymizing Social Network Graphs

Kayem, Anne V.D.M. and Deshai, Azhar and Hammer, Stuart (2012) On Anonymizing Social Network Graphs, Proceedings of 11th Information Security Conference (ISSA 2012), August 15-17, 2012, Johannesburg, South Africa, 1-8, IEEE.

Full text not available from this repository. (Use alternate locations listed below)


The proliferation of social networks as a means of seamless communication between multiple parties across vast geographical distances has driven an increased interest from government organizations and companies. Government organizations typically seek access to these pools of personal data for statistical purposes while companies tend to look at this data from a marketing perspective. Users typically post information containing personal data during social network interactions with other users because the aim is to share this information only with persons that are authorized to access the information. However, the growing desire to exploit this information for statistical and marketing purposes, for instance, raises the question of privacy. It is therefore increasingly important to come up with ways of anonymizing personal data in order to circumvent privacy violations. Previous work has focused on two major approaches to anonymizing data namely, clustering and graph modifications. Both techniques aim to preserve the utility of the data for analysis and keep the identities of the users secret. We postulate however, that both approaches are in fact vulnerable to privacy violations and so do not enforce the property of anonymity. In addition, we argue that this problem is in fact NP-Hard and that the difficulty is in identifying as well as anonymizing all the possible channels that might leak information about a person’s true identity.

Item Type: Conference paper
Subjects: Computer systems organization > Architectures > Other architectures
General and reference > Document types > Surveys and overviews
Theory of computation > Design and analysis of algorithms
Theory of computation > Design and analysis of algorithms > Data structures design and analysis
Date Deposited: 02 Nov 2012
Last Modified: 10 Oct 2019 15:33
URI: http://pubs.cs.uct.ac.za/id/eprint/821

Actions (login required)

View Item View Item