Journal
SOCIAL NETWORK ANALYSIS AND MINING
Volume 3, Issue 2, Pages 151-166Publisher
SPRINGER WIEN
DOI: 10.1007/s13278-012-0059-7
Keywords
Privacy; Social networks; Complexity; k-Anonymity; Table graphs
Categories
Ask authors/readers for more resources
With an abundance of social network data being released, the need to protect sensitive information within these networks has become an important concern of data publishers. To achieve this objective, various notions of k-anonymization have been proposed for social network graphs. In this paper we focus on the complexity of optimization problems that arise from trying to anonymize graphs, establishing that optimally k-anonymizing the label sequences of edge-labeled graphs is intractable. We show how this result implies intractability for other notions of k-anonymization in literature. We also consider the case of bipartite social network graphs which arise from the representation of distinct entities, such as movies and viewers, patients and drugs, or products and customers. Within this setting we demonstrate that, although k-anonymizing edge-labeled graphs is intractable for k >= 3, polynomial time algorithms exist for arbitrary bipartite graphs when k = 2 and for unlabeled bipartite graphs irrespective of the value of k. Finally, in this paper we extend the study of attribute disclosure within the context of social networks by defining t-closeness, a measure of how effectively an adversary can determine sensitive information about members of a k-anonymous social network.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available