Towards link inference attack against network structure perturbation

Abstract The increasing popularity and diversity of social media sites have resulted in an emergent number of available social networks. These social networks are now the source of information for third-party consumers, such as researchers and advertisers, to understand user social activities. In a privacy-preserving viewpoint, a full assessment of social relationships between individuals may violate privacy. Different network structure perturbation methods have been proposed to limit the disclosure of sensitive user data. However, despite the proliferation of these methods, currently, there are no robustness studies on the methods for link prediction-based hidden inference structure. In this study, we survey the state-of-the-art network structure perturbation methods for privacy-preservation and the classic link prediction methods for structure inference. To restore the perturbed network structure effectively, we propose a novel Multi-Layer Linear Coding-based link prediction method (MLLC) with a closed-form solution. Furthermore, we provide vulnerability analysis on network structure perturbation methods in the context of link prediction-based structure inference. We also compare the methods on the preservation of utility metrics for social network analysis, where a structure perturbation method is preferred if the metrics of the perturbed network are similar to those of the original network. Our experimental study indicates that the MLLC algorithm outperforms conventional methods for hidden structure inference, and that it is important to provide robustness to network structure perturbation methods against these attacks.