On the Privacy of Anonymized Networks
The proliferation of online social networks, and the concomitant accumulation of user data, give rise to hotly debated issues of privacy, security, and control. One specific challenge is the sharing or public release of anonymized data without accidentally leaking Personally Identifiable Information (PII). Unfortunately, it is often difficult to ascertain that sophisticated statistical techniques, potentially employing additional external data sources, are unable to break anonymity. In this paper, the authors consider an instance of this problem, where the object of interest is the structure of a social network, i.e., a graph describing users and their links.