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.