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

摘要

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.