Towards Preventing Neighborhood Attacks: Proposal of a New Anonymization’s Approach for Social Networks Data

Anonymization is a crucial process to ensure that published social network data does not reveal sensitive user information. Several anonymization approaches for databases have been adopted to anonymize social network data and prevent the various possible attacks on these networks. In this paper, we will identify an important type of attack on privacy in social networks: “neighborhood attacks”. But it is observed that the existing anonymization methods can cause significant errors in certain tasks of analysis of structural properties such as the distance between certain pairs of nodes, the average distance measure “APL”, the diameter, the radius, etc. This paper aims at proposing a new approach of anonymization for preventing attacks from neighbors while preserving as much as possible the social distance on which other structural properties are based, notably APL. The approach is based on the principle of adding links to have isomorphic neighborhoods, protect published data from neighborhood attacks and preserve utility on the anonymized social graph. Our various experimental results on real and synthetic data show that the algorithm that combines the addition of false nodes with the addition of links, allows to obtain better results compared to the one based only on the addition of links. They also indicate that our algorithm preserves average distances from the existing algorithm because we add edges between the closest nodes.