Attribute Couplet Attacks and Privacy Preservation in Social Networks

The emerging of social networks, e.g., Facebook, Twitter, and Instagram, has eventually changed the way in which we live. Social networks are acquiring and storing a significant amount of profile information and daily activities of over billions of active users. The data sets, drawn from the social networks, are becoming great sources for exploring and attracting huge interests from different research communities. However, publishing social network data sets have also raised serious security and privacy risks; it is highly likely that they will be targeted by the hackers due to their substantially commercial values. To deal with the problem of privacy leakage, a number of attack models and corresponding privacy preserving solutions have been proposed recently. A common approach is to anonymize the identities of the users when publishing the data sets while we argue that the remaining relationship is sufficient to identify an anonymized user. In this paper, we define a new type of attack as attribute couplet attack. The attribute couplet attack facilitates the relationship of a couplet of anonymous nodes (i.e., a pair of users) and some limited background information to unveil the protected identities. To achieve privacy-preservation under attribute couplet attacks, we propose a new anonymity concept as k-couplet anonymity. A social network data set satisfies the k-couplet anonymity if, for any pair of nodes, there exist at least the other k - 1 couplets sharing the same attributes. Then, we design and implement two heuristic algorithms to promote the k-couplet anonymity. Furthermore, we design an approximate algorithm for multiple-attribute social networks to realize the k-couplet anonymity. The evaluation results on multiple data sets demonstrate that the privacy and utility of the social network data sets can be well preserved, when incorporating the proposed k-couplet anonymity and the associate heuristic algorithms.