UCT CS Research Document Archive

On Anonymizing Social Network Graphs

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

Full text available as:

Abstract

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.

EPrint Type:Conference Paper
Subjects:C Computer Systems Organization: C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
A General Literature: A.1 INTRODUCTORY AND SURVEY
F Theory of Computation: F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
E Data: E.1 DATA STRUCTURES
ID Code:821
Deposited By:Kayem, AVDM
Deposited On:02 November 2012