Graph Perturbation as Noise Graph Addition: A New Perspective for Graph Anonymization

Abstract

Different types of data privacy techniques have been applied to graphs and social networks. They have been used under different assumptions on intruders’ knowledge. i.e., different assumptions on what can lead to disclosure. The analysis of different methods is also led by how data protection techniques influence the analysis of the data. i.e., information loss or data utility. One of the techniques proposed for graph is graph perturbation. Several algorithms have been proposed for this purpose. They pro- ceed adding or removing edges, although some also consider adding and removing nodes. In this paper we propose the study of these graph perturbation tech- niques from a different perspective. Following the model of standard database perturbation as noise addition, we propose to study graph per- turbation as noise graph addition. We think that changing the perspec- tive of graph sanitization in this direction will permit to study the prop- erties of perturbed graphs in a more systematic way.