Against Signed Graph Deanonymization Attacks on Social Networks

Privacy protection is one of the most challenging problems of social networks. Simple removal of the labels is unable to protect the privacy of social networks because the information of graph structures can be utilized to deanonymize target nodes. Previous related proposals mostly assume that attacker knows only the target's neighborhood graph, but ignoring of signed edge attribute. The graph structure with signed edge attributes could cause serious privacy leakage of social networks. In this paper, we take the signed attribute of edges into account when achieving k-anonymity privacy protection for social networks. We propose a signed k-anonymity scheme to protect the privacy of key entities in social networks. With signed k-anonymity protection, these targets cannot be re-identified by attackers with confidence higher than 1 / k. The proposed scheme minimizes the modification, which preserves high utility of the original data. Extensive experiments on real data sets and synthetic graph illustrate the effectiveness of the proposed scheme.