An evaluation of vertex and edge modification techniques for privacy-preserving on graphs

Noise is added by privacy-preserving methods or anonymization processes to prevent adversaries from re-identifying users in anonymous networks. The noise introduced by the anonymization steps may also affect the data, reducing its utility for subsequent data mining processes. Graph modification approaches are one of the most used and well-known methods to protect the privacy of the data. These methods convert the data by means of vertex and edge modifications before releasing the perturbed data. In this paper we want to analyze the vertex and edge modification techniques found in literature covering this topic. We empirically evaluate the information loss introduced by each of these methods not only using generic metrics related to graph properties, but also using some specific metrics related to real graph-mining tasks. We want to point out how these methods affect the main properties and characteristics of the network, since it will help us to choose the best one to achieve a desired privacy level while preserving data utility.