Vertex re-identification attack using neighbourhood-pair properties

There has been a growing interest in sharing and mining social network data for a wide variety of applications. In this paper, we address the problem of privacy disclosure risks that arise from publishing social network data. Specifically, we look at the vertex re-identification attack that aims to link specific vertex in social network data to specific individual in the real world. We show that even when identifiable attributes such as names are removed from released social network data, re-identification attack is still possible by manipulating abstract information. We present a new type of vertex re-identification attack model called neighbourhood-pair attack. This attack utilizes the information about the local communities of two connected vertices to identify the target individual. We show both theoretically and empirically that the proposed attack provides higher re-identification rate compared with the existing re-identification attacks that also manipulate network structure properties. The experiments conducted also show that the proposed attack is still possible even on anonymised social network data.