## 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)
```
0:\(NS_{dout}\), \(NS_{din}\), \(S_{dout}\), \(S_{din}\), a directed sub-graph \(S_{Gi}\) = (\(V_{i}\), \(E_{i}\))
0: a synthesis directed sub-graph \(Sn_{Gi}\)
1:\(Sn_{Gi}\gets S_{Gi}\)
2: ( \(Do_{1}\), \(Do_{2}\)) \(\leftarrow\) comparing \(S_{dout}\) with \(NS_{dout}\)
3: (\(Di_{1}\), \(Di_{2}\)) \(\leftarrow\) comparing \(S_{din}\) with \(NS_{din}\)
4: Sorting \(Do_{1}\) and \(Di_{1}\) from large to small
5: for node \(i\) in \(Do_{1}\):
6: \(k\) = \(Do_{1}\)[i]
7: if \(|Di_{1}|>0\)
8: selecting \(k\) nodes \(D_{i1}\) and adding edges from node \(i\) to those \(k\) nodes in \(S_{Gi}\)
```  
**Algorithm 4** GGM algorithm ```
9: modifying the values of those \(k\) nodes in \(Di_{1}\)
10: if the values of node \(j\) in \(Di_{1}\) nodes \(<0\):
11: abandoning node \(j\) from \(Di_{1}\)
12: if sum (\(Do_{2}\)) \(>\) sum ( \(Di_{2}\))
13: for node \(i\) in \(Do_{2}\):
14: \(k=Do_{2}\)[i]
15: a set of node \(N_{a}=\) neighborhood nodes of node \(i\)
16: a set of node \(IN_{a}=\) intersection of \(N_{a}\) and nodes in \(Di_{2}\)
17: if \(|IN_{a}|>\)0
18: selecting min \(\{\text{k}_{i}|IN_{a}|\}\) nodes from \(IN_{a}\) and deleting edges from node \(i\) to those nodes
19: else:
20: selecting min \(\{\text{k}_{i}|N_{a}|\}\) nodes from \(N_{a}\) and deleting edges from node \(i\) to those nodes
21: else:
22: for node \(i\) in \(Di_{2}\):
23: \(k=Di_{2}\)[i]
24: a set of node \(Na=\) predecessors nodes of node \(i\)
25: a set of node \(Ina=\) intersection of Na and nodes in \(Do_{2}\)
26: if number of \(Ina>\) 0
27: selecting min \(\{\text{k}_{i}|IN_{a}|\}\) nodes from \(IN_{a}\) and deleting edges from node \(i\) to those nodes
28: else:
29: selecting min \(\{\text{k}_{i}|N_{a}|\}\) nodes from \(N_{a}\) and deleting edges from node \(i\) to those nodes
30: Return \(Sn_{Gi}\)
```

**Algorithm 4**_Cont._

#### 4.2.4 Analysis of DGNDP Algorithm

**Theorem 1**. : _The GSEM algorithm satisfies \(\varepsilon\)-differential privacy._

Proof of Theorem 1.: As discussed before, the probability to select the threshold \(t\) is

\[p_{r}(t)=\frac{\exp\left(-\frac{\varepsilon U(Sg,t)}{2\Delta U}\right)}{\sum_{ t^{{}^{\prime}}\in\mathcal{O}}\exp\left(-\frac{\varepsilon U(Sg,t^{{}^{\prime}})}{2 \Delta U}\right)}\]

In this algorithm, we assumed \(Sg\) and \(Sg^{{}^{\prime}}\) are neighborhood graphs, where there is one node difference between them. For any variable \(t\), the following result is obtained. \[\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)}}\]

\[=\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)\]\[\leq\exp\Bigl{(}\frac{\varepsilon}{2}\Bigr{)}\times\exp\Bigl{(} \frac{\varepsilon}{2}\Bigr{)}\times\Biggl{(}\frac{\sum_{i^{\prime}\in 0}\exp\Bigl{(}-\frac{tUl(SG^{\prime})}{2 Ul} \Bigr{)}}{\sum_{i^{\prime}\in 0}\exp\Bigl{(}-\frac{tUl(SG^{\prime})}{2 Ul}\Bigr{)}} \Biggr{)}\] \[\leq\exp\Bigl{(}\frac{\varepsilon}{2}\Bigr{)}\times\exp\Bigl{(} \frac{\varepsilon}{2}\Bigr{)}\times\Biggl{(}\frac{\sum_{i^{\prime}\in 0}\exp\Bigl{(}-\frac{tUl(SG^{\prime})}{2 Ul} \Bigr{)}}{\sum_{i^{\prime}\in 0}\exp\Bigl{(}-\frac{tUl(SG^{\prime})}{2 Ul}\Bigr{)}} \Biggr{)}\] \[=\exp(\varepsilon)\]

It is clear that the process of selecting the threshold \(t\) satisfies differential privacy. In addition, in view of the principle of post-processing, it satisfies differential privacy to obtain an out-degree sequence and an in-degree sequence from the input graph through the exponent mechanism.