## 4 The Proposed Method
### DGNDP (Synthetic Directed Graph Based on Node Differential Privacy) Algorithm
#### 4.2.3. GGM (Generating Synthetic Graph Based on Graph Modification)
### Results and Discussion

#### 5.3.1 Analysis of Privacy Preservation

At first, the proposed method is conducted in the five data sets and the results are kept in \[\frac{p_{r}(E(Sg,t))}{p_{r}(E(Sg,t))}=\frac{\frac{\exp\left(-\frac{ \varepsilon U(Sg,t)}{2\Delta U}\right)}{\exp\left(-\frac{\varepsilon U(Sg,t^{ {}^{\prime}})}{2\Delta U}\right)}}{\frac{\exp\left(-\frac{\varepsilon U(Sg,t^{ {}^{\prime}})}{2\Delta U}\right)}{\sum_{t^{{}^{\prime}}\in\mathcal{O}}\exp \left(-\frac{\varepsilon U(Sg,t^{{}^{\prime}})}{2\Delta U}\right)}}\]9 As shown in Table 1, when \(k\) is 3 and \(\varepsilon\) is 1, the value of \(CRE\) in the Hamsterster friendships data set is 47.62, while that in the Gnutella data set is 49.76. In particular, the value of \(CRE\) increases along with the decrease of \(\varepsilon\) when \(k\) is fixed. For example, when \(k\) is 3, the value of \(CRE\) in the Wikipedia\(-\)link data set increases from 25.74 to 69.13 with \(\varepsilon\) decreasing from 2 to 0.2, while that in the Gnutella data set also changes from 36.32 to 71.38. The results show that the smaller the \(\varepsilon\), the larger \(CRE\), which indicates that the proposed method can gain better privacy preservation for data sets. In Table 2, when \(\varepsilon\) is 1, if the \(k\) increases from 2 to 5, the value of \(CRE\) in Wikipedia-link will decrease from 50.89 to 36.74, as does that in other data sets, which indicates that the value of \(k\) can affect the privacy preservation. It is clearer that the smaller \(k\), the better privacy preservation. \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline \multirow{2}{*}{\(K\)} & \multirow{2}{*}{\(\varepsilon\)} & \multirow{2}{*}{**Physicians**} & \multicolumn{2}{c}{**Hamsterster**} & \multirow{2}{*}{**Wikipedia\(-\)Link**} & \multirow{2}{*}{**Gnutella**} & \multirow{2}{*}{**Twitter Lists**} \\  & & & & & & \\ \hline
3 & 0.2 & 72.32 & 74.38 & 69.13 & 71.38 & 68.18 \\
3 & 0.5 & 61.25 & 58.23 & 57.79 & 60.32 & 56.67 \\
3 & 1 & 50.13 & 47.62 & 57.21 & 49.76 & 45.23 \\
3 & 1.5 & 43.62 & 41.87 & 38.11 & 43.98 & 40.62 Then, the performance of the proposed method in Gnutella and Twitter lists is illustrated in Figures 4 and 5. In Figure 4, with \(\varepsilon\) increasing from 0.2 to 2, the value of _CRE_ decreases from about 70 to about 30 regardless of the value of \(k\), which indicates that the \(\varepsilon\) controls the degree of privacy preservation. In addition, no matter what the value of \(\varepsilon\) is, the value of _CRE_ increases with \(k\) decreasing from 5 to 2, which shows that the micro-aggregation can control privacy preservation. In addition, the same results as that in Figure 4 are demonstrated in Figure 5, which implies that the proposed method also can be applied in the big network. In the end, the proposed method is compared with other methods, and the results are illustrated in Figures 6 and 7. In Figure 6, when \(\varepsilon\) is 1, the value of _CRE_ obtained by the proposed method is larger than that in (ki,ko)-degree anonymity method and \(k\)-anonymity method regardless of the value of \(k\). Although the values in the (ki,ko)-degree anonymity method and \(k\)-anonymity method increase with the value of \(k\) rising, the proposed method provides better privacy preservation than these two methods. However, compared with the value of _CRE_ in the proposed method without micro-aggregation, the value of _CRE_ in the proposed method is smaller regardless of the value of \(k\), which shows that the micro-aggregation can weaken privacy preservation.