## 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)
Moreover, in the data set Twitter lists, the same results as that in Figure 6 are shown in \[=\left(\frac{\exp\left(-\frac{\varepsilon U(Sg,t)}{2\Delta U}\right)}{\exp \left(-\frac{\varepsilon U(Sg,t^{{}^{\prime}})}{2\Delta U}\right)}\right) \times\left(\frac{\sum_{t^{{}^{\prime}}\in\mathcal{O}}\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)}\right)\]0 Therefore, the proposed method provides better privacy preservation than the two anonymity methods and has better data utility than the method without micro-aggregation. \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline \(K\) & \(\varepsilon\) & **Physicians** & **Hamsterster Friendships** & **Wikipedia\(-\)Link** & **Gnutella** & **Twitter Lists** \\ \hline
2 & 1 & 56.39 & 52.14 & 50.89 & 54.67 & 51.22 \\
3 & 1 & 50.13 & 47.62 & 45.21 & 49.76 & 45.23 \\
4 & 1 & 45.82 & 43.68 & 40.31 & 45.33 & 41.87 \\
5 & 1 & 41.22 & 39.98 & 36.74 & 40.79 & 38.49 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: The value of CRC in proposed method when \(\varepsilon=1\). Figure 4: The comparison in the different privacy budgets in Wikipedia. Figure 5: The comparison of the different privacy budgets in Twitter lists. To sum up, the experiment results show that the proposed method can preserve directed graphs. In addition, micro-aggregation can be applied to control privacy preservation in this method. #### 5.3.2 Analysis of Data Utility

As shown in Figure 8, when the \(\varepsilon\) is 1, with \(k\) rising, the values of \(El\) in five data sets all increase, which means more and more edges in the original graph retained in the synthetic directed graph generated by the proposed method. In Figure 9, as the \(\varepsilon\) is 1, the value of \(\triangle\)_av-\(Cb\)_ decreases gradually with the value of \(k\) increasing. The result indicates the property of nodes in the synthetic directed graph is close to that of the original directed graph. As illustrated in Figures 10 and 11, it is clear that the \(\triangle\)_av-in_\(Cc\) and the \(\triangle\)_av-out_\(Dc\) decline with \(k\) rising. To sum up, the results show that the proposed method can provide effective data utility. Figure 8: The comparison of EI in the different data sets. Figure 6: The comparison of the different methods in Wikipedia. Figure 7: The comparison of the different methods in Twitter lists. In particular, with the size of the network and the amount of data increasing, the computational overhead significantly increases because more and more edges and nodes are modified. In order to preserve a large directed graph, it is divided into many subgraphs. Compared with the original directed graph, each sub-graph is much smaller. Therefore, the proposed algorithms can be well applied in these sub-graphs. In real-world deployments, for the scalability of the method, the scalability of the Louvain algorithm is mainly considered, which determines the scalability of the proposed method. ## 6 Conclusions

In this paper, to preserve directed graphs in MWNs, the DGNDP method is designed, which combines node differential privacy and graph modification. In this method, as node differential privacy can provide stronger privacy preservation than edge differential privacy and graph modification, it is used to add noise on degree sequences. Then, edge modification utilizes noised degree sequences to generate a synthetic directed graph, which

Figure 11: The comparison of the average of our Dc in the different data sets. Figure 10: The comparison of the average of in Cc in the different data sets. Figure 9: The comparison of betweenness in the different data sets. can strongly preserve the original directed graph. Additionally, to improve data utility, the original directed graph is divided into many sub-graphs, and the perturbations are only added in each sub-graph.