Neighbourhood-pair attack in social network data publishing

Vertex re-identification is one of the significant and challenging problems in social network. In this paper, we show a new type of vertex reidentification attack called neighbourhood-pair attack. This attack utilizes the neighbourhood topologies of two connected vertices. We show both theoretically and empirically that this attack is possible on anonymized social network and has higher re-identification rate than the existing structural attacks.