Advances in technology have made it possible to collect data about individuals and the connections between them, such as email correspondence and friendships. Agencies and researchers who have collected such social network data often have a compelling interest in allowing others to analyze the data. However, in many cases the data describes relationships that are private (e.g., email correspondence) and sharing the data in full can result in unacceptable disclosures. In this paper, we present a framework for assessing the privacy risk of sharing anonymized network data. This includes a model of adversary knowledge, for which we consider several variants and make connections to known graph theoretical results. On several real-world social networks, we show that simple anonymization techniques are inadequate, resulting in substantial breaches of privacy for even modestly informed adversaries. We propose a novel anonymization technique based on perturbing the network and demonstrate empirically that it leads to substantial reduction of the privacy threat. We also analyze the effect that anonymizing the network has on the utility of the data for social network analysis. Figure 1: A social network, G; the naive anonymization of G; the anonymization mapping. Similarly, researchers in the field of computer networking analyze internet topology, internet traffic and routing properties using network traces that can now be collected at line speeds at the gateways of institutions and by ISPs. These traces represent a social network where the entities are internet hosts and the existence of communication between hosts constitutes a relationship. However network traces (even with packet content removed) contain sensitive information because it is often possible to associate individuals with the hosts they use, and because traces contain information about web sites visited, and time stamps which indicate periods of activity. The challenges in protecting network trace data are being actively addressed by the research community [22] . Our goal is to enable the useful analysis of social network data while protecting the privacy of individuals. Much recent work has focused on managing the balance between privacy and utility in data publishing, but only for certain limited datasets. For example, k-anonymity [25] , and its variants [12, 15, 17] , are data perturbation techniques designed for tabular micro-data, which typically consists of a table of records each describing an entity. While useful for census databases and some medical information, these techniques cannot address the fundamental challenge of managing social network datasets. Other work has considered different kinds of data, such as item set transactions [10] and OLAP data [2]. However, a common assumption underlying all of these techniques is that the records are independent and can be anonymized (more or less) independently. In contrast, social network data forms a graph of relationships between entities. Existing tabular perturbation techniques are not equipped to operate over graphs-they will tend to ignore and destroy important structural properties. Likewise, graph structure and background knowledge combine to threaten privacy in new ways.
The work in REF quantified the privacy risks associated with different kinds of attacks on social networks, and proposed a randomization method to perturb the graph.
Anonymizing Social Networks
VLDB 2008
Computer Science