Privacy Preserving Social Network Publication Against Mutual Friend Attacks
This addresses privacy concerns for individuals in social network research by proposing a novel defense against a specific attack, though it is incremental as it builds on existing anonymity concepts.
The authors tackled the problem of mutual friend attacks in social network data publication by introducing a new privacy attack model and proposing k-NMF anonymity to protect friend pairs based on their number of mutual friends, with experimental results showing effective privacy and utility preservation on real-world datasets.
Publishing social network data for research purposes has raised serious concerns for individual privacy. There exist many privacy-preserving works that can deal with different attack models. In this paper, we introduce a novel privacy attack model and refer it as a mutual friend attack. In this model, the adversary can re-identify a pair of friends by using their number of mutual friends. To address this issue, we propose a new anonymity concept, called k-NMF anonymity, i.e., k-anonymity on the number of mutual friends, which ensures that there exist at least k-1 other friend pairs in the graph that share the same number of mutual friends. We devise algorithms to achieve the k-NMF anonymity while preserving the original vertex set in the sense that we allow the occasional addition but no deletion of vertices. Further we give an algorithm to ensure the k-degree anonymity in addition to the k-NMF anonymity. The experimental results on real-word datasets demonstrate that our approach can preserve the privacy and utility of social networks effectively against mutual friend attacks.