Journal
SOCIAL NETWORK ANALYSIS AND MINING
Volume 3, Issue 3, Pages 381-399Publisher
SPRINGER WIEN
DOI: 10.1007/s13278-012-0084-6
Keywords
Privacy; k-Anonymization; Social networks; Complexity; Dynamic programming
Categories
Ask authors/readers for more resources
For a graph-based representation of a social network, the identity of participants can be uniquely determined if an adversary has background structural knowledge about the graph. We focus on degree-based attacks, wherein the adversary knows the degrees of particular target vertices and we aim to protect the anonymity of participants through k-anonymization, which ensures that every participant is equivalent to at least k - 1 other participants with respect to degree. We introduce a natural and novel approach of introducing dummy'' participants into the network and linking them to each other and to real participants in order to achieve this anonymity. The advantage of our approach lies in the nature of the results that we derive. We show that if participants have labels associated with them, the problem of anonymizing a subset of participants is NP-Complete. On the other hand, in the absence of labels, we give an O(nk) algorithm to optimally k-anonymize a subset of participants or to near-optimally k-anonymize all real and all dummy participants. For degree-based-attacks, such theoretical guarantees are novel.
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