## 4 The Proposed Method
### DGNDP (Synthetic Directed Graph Based on Node Differential Privacy) Algorithm
#### 4.2.1 GSEM (Generating Degree Sequence Based on Exponent Mechanism) Algorithm
From line 3 to line 5, the exponent mechanism is used to get a threshold \(t\). In line 6, an out-degree sequence \(Seq_{out}\) is truncated to get an out-degree sequence \(S_{dout}\), and it is returned in line 7. ```
Input: a directed \(S_{Ga}\) = (\(V_{a}\), \(E_{a}\)), a privacy budget \(\epsilon_{1}\) Output: an out-degree sequence \(S_{dout}\)
1: an out degree sequence\(Seat_{out}\leftarrow\) a directed graph \(S_{Ga}\) = ( \(V_{a}\), \(E_{a}\))
2:\(d_{max}\)= the maximum degree of \(Seq_{out}\)
3: for 1 to \(t\):
4: the scoring function \[Error(Seq_{out}\)(S\({}_{Ga}\))\]7
5: selecting \(t\) with probability \[Error(Seq_{out}\)(S\({}_{Ga}\))\]8
6: an out-degree sequence \(S_{dout}\leftarrow\) an out degree sequence\(Seat_{out}\)
7: Return an out-degree sequence \(S_{dout}\)
```  
**Algorithm 2** GSEM algorithm  
.2.2 ADPRA (Adding Noise Based on Differential Privacy with the Ranking Micro-Aggregation) Algorithm  
Given an ordered degree sequence \(d\) = [\(d_{1}\), \(d_{2}\),..., \(d_{n}\)], it is aggregated into \(\frac{n}{k}\) clusters. In each cluster, there are \(k\) continuous degree values, except perhaps one cluster that contains up to \(2k-1\) consecutive values. Then, there is a sequence of the centroid of these clusters denoted by [\(dc_{1}\), \(dc_{2}\),..., \(dc_{n/k}\)]. In this ordered degree sequence, if any single \(d_{i}\) in \(d\) is replaced by \(\tilde{d}\), \(|d_{i}-\tilde{d}|\leq\triangle\), then there is a new sequence of the centroid of these new clusters which is described as [\(d\tilde{c}_{1}\), \(d\tilde{c}_{2}\),..., \(d\tilde{c_{n/k}}\)]. As a result, it holds that  
\[Error(Seq_{out}\)(S\({}_{Ga}\))\]9  
Compared with edge differential privacy, node differential privacy can provide stronger privacy preservation. Nevertheless, node differential privacy results in insufficient data utility. To mitigate this problem, the ranking micro-aggregation is introduced to improve data utility. In particular, with the help of the ranking micro-aggregation, this algorithm generates two differential private degree sequences with effective data utility, which are useful for the graph modification in the next step. Without losing generality, assume \(\bar{d}_{i}>d_{i}\), and \(n\) can be divided by \(k\). Thus, there are \(n\)/\(k\) clusters, with each cluster \(m\) having consecutive values from \(d_{(m-1)k+1}\) to \(d_{mk}\). In particular, each \(d_{i}\) belongs to a cluster \(m_{i}\). Then two cases are discussed. Case 1: if \(\bar{d}_{i}\leq d_{m,k+1}\), then is still in cluster \(\bar{m}_{i}\). Except for the cluster \(m_{i}\), the centroids of other clusters are unchanged. The centroids of the cluster \(\bar{m}_{i}\) increase \(\frac{\Delta}{k}\), because \(\bar{d}_{i}=d_{i}+\bigtriangleup\). Therefore, this case meets the requirements of the ranking micro-aggregation. Case 2: if \(\bar{d}_{i}\geq d_{m,k+1}\), then \(\bar{d}_{i}\) is not in cluster \(m_{i}\). Therefore, two and more changes for the \(\bar{d}_{i}\) replace the \(d_{i}\): the clusterm\(m_{i}\) lose \(d_{i}\) and a cluster \(\bar{m}_{i}\) obtain \(\bar{d}_{i}\)(for \(\bar{m}_{i}>m_{i}\)). For keeping the number of clusters \(m_{i}\) unchanged, the cluster \(m_{i}\) gains \(d_{m,k+1}\); in return, the cluster \(m_{i}\)+1 loses \(d_{m,k+1}\) and obtains \(d_{m_{i+1}+k+1}\), until the cluster \(\bar{m}_{i}\) gives its smallest value \(d_{(m_{i}-1)k+1}\) to cluster \(\bar{m}_{i}-1\) and obtains \(\bar{d}_{i}\). From cluster \(\bar{m}_{i}+1\) to the end cluster, there is nothing that takes place. The change of the centroids is shown as follows:  
\[=RE(Seq_{out}(\text{S}_{Ga}))+LE(Seq_{out}(\text{S}_{Ga}))\]0 \[=RE(Seq_{out}(\text{S}_{Ga}))+LE(Seq_{out}(\text{S}_{Ga}))\]1 \[=RE(Seq_{out}(\text{S}_{Ga}))+LE(Seq_{out}(\text{S}_{Ga}))\]2 \[=RE(Seq_{out}(\text{S}_{Ga}))+LE(Seq_{out}(\text{S}_{Ga}))\]3 \[=RE(Seq_{out}(\text{S}_{Ga}))+LE(Seq_{out}(\text{S}_{Ga}))\]4  
when \(n\) is not a multiple of \(k\), there are \(n\)/\(k\) clusters and one of them holds values between \(k+1\) and \(2k-1\).