High-degree noise addition method for the k-degree anonymization algorithm

What is it about?

Social network datasets are a valuable source of information for academic researches as well as business and marketing studies. Since social network datasets contain personal and sensitive information of their users, sharing the data with a third party gives rise to many privacy-preserving issues. The k -degree anonymization was developed to protect the users of social networks from the re-identification attack by modifying the network structure with a sequence of edge editing operations. In this paper, we introduce a novel approach for noise addition operation in the well-known k -degree anonymization algorithm k -DA. We propose the high-degree noise addition method that modifies the degree sequence anonymized by the degree anonymization procedure of k -DA before it is processed by the graph construction procedure of k -DA. Our proposed method significantly reduces the number of necessary repetitions of the graph constructing algorithm and positively affects the efficiency and runtime of the whole k -DA algorithm. Moreover, we show that the proposed high-degree noise addition algorithm improves k -DA in terms of data utility. We demonstrate its usability by running experiments on 13 different real-world social network datasets.

Featured Image