Protecting Anonymity in Published Social Networks
Gerome Miklau, University of Massachusetts at Amherst


Social network analysis is concerned with uncovering patterns in graph-structured data sets
describing entities and the social connections between them. It has been widely applied to
study the influence or popularity of individuals in organizations, disease transmission in
communities, the operation of computer networks, and the emergent behavior of physical and
biological systems. While extremely valuable to analysts, social network data often
describes relationships that are sensitive and sharing the data in full can result in
unacceptable disclosures.

In this talk, I will describe threats to anonymity posed by published networks, and our
initial work on resisting these threats. I will focus on the threat of structural
re-identification, in which an individual's local relationships can be identifying even when
their names are removed from the graph. Re-identification risk depends on the power of the
adversary and also the naturally-occurring structural diversity in the graph. I will present
a range of models of adversary knowledge and evaluate their impact on anonymity using both
empirical results on real networks, and models of random graphs. Finally, I will describe an
anonymization technique based on graph clustering which can accurately preserve global
properties of networks while protecting against re-identification.

(This talk is based on joint work with Michael Hay and David Jensen.)