## 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)
\[\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)}}\]1

\[\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)}}\]2

\[\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)}}\]3\[\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)}}\]4 \[\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)}}\]5 \[\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)}}\]6

The DGNDP algorithm satisfies \(\epsilon\)-differential privacy. Proof of Theorem 3.: In this algorithm, each sub-graph is handled by the GSEM algorithm and ADPRA algorithm, which all satisfy differential privacy. According to the principle of sequence combination in differential privacy, each sub-graph is preserved by differential privacy. After all the sub-graphs are merged into a complete directed graph, on the basis of the principle of parallel processing in differential privacy, it is evident that the GDNDP algorithm satisfies differential privacy. ## 5 Experiments and Results

In this paper, the proposed method focuses on a special directed graph, which is a simple connected directed graph without self-cycles and node attributes. In this section, five real-world data sets, which describe five directed graphs are applied to demonstrate the efficiency of the proposed method. In privacy preservation, the change rate of the edge is utilized to evaluate the performance of methods. In data utility, the metrics of the graph are used to measure the effectiveness of methods. In addition, we compare the proposed method with other methods in [5; 20]. The experiments are conducted on a Laptop with an Intel i7 3.5 Ghz and 8 GB RAM, which works with Windows10 and Python 2.6. ### Data Sets

1. Physicians: This directed network captures innovation spread among 246 physicians in towns in Illinois, Peoria, Bloomington, Quincy, and Galesburg. A node represents a physician and an edge between two physicians shows that the left physician told that the right physician is his friend or that he turns to the right physician if he needs advice or is interested in a discussion. There are 240 nodes and 1098 edges. 2. Blogs: This directed network contains front-page hyperlinks between blogs in the context of the 2004 US election.