## 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)
A node represents a blog and an edge represents a hyperlink between two blogs. There are 1224 nodes and 19,025 edges. 3. Wikipedia - link: This network consists of the wikilinks of Wikipedia in the Gagauz language (gag). Nodes are Wikipedia articles and directed edges are wikilinks, i.e., hyperlinks within one wiki. There are 2929 nodes and 118,603 edges. 4. Gnutella: This is a network of Gnutella hosts from 2002. The nodes represent Gnutella hosts, and the directed edges represent connections between them. There are 12,717 nodes and 51,525 edges. 5. Twitter lists: This directed network contains Twitter user-user following information. A node represents a user. An edge indicates that the user represented by the left node follows the user represented by the right node. There are 23,370 nodes and 1,231,177 edges. ### Metrics and Parameters

#### 5.2.1 Metrics and Parameters in Privacy Preservation

To evaluate privacy preservation, a metric, the change rate of the edge is shown as follows. \[\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)}}\]7where \(M_{e}\) denotes the sum of all edges that are added and deleted in this method and \(S_{e}\) represents the sum of edges of the synthesis graph. This metric indicates how much the original graph has been modified to generate a synthesis graph. The larger \(CRC\), the better privacy preservation. Moreover, three methods including the independent (\(ki\), \(ko\))-degree anonymity method in [5], \(k\)-anonymity method in [20] and the GDGMP method without micro-aggregation are used to compare with the proposed method. The method in reference [5] is a k-degree anonymity method without considering the direction of edges, which minimizes changes in degree sequences as much as possible. Compared with the method in reference [5], the method in reference [20] focuses on directed graphs and provides a k-degree anonymity method. As node differential privacy can provide stronger privacy preservation than k-anonymity methods, the proposed method achieves better privacy preservation for directed graphs. Correspondingly, the privacy budget in experiments is set as the sum of \(\varepsilon 1\) and \(\varepsilon 2\), where \(\varepsilon 1=\varepsilon 2=\varepsilon\). Meanwhile, \(\varepsilon\) is in [0.2, 0.5, 1.0, 1.5, 2] and \(k\), the number of elements in a cluster, is the integer between 2 and 5, which is also used in \(k\)-anonymization. Due to the uncertainty of the noise, all data sets are executed 10 times by using the proposed method and other methods to average out the results. #### 5.2.2 Metrics and Parameters in Data Utility

In the graph structure measure, the edge intersection \(EI\) is the ratio of the edges in the original graph to edges in the perturbed graph, as shown below. \[\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)}}\]8

In the properties of nodes, the betweenness centrality(\(Cb\)) is the fraction of the shortest paths that go through each node. Then, the closeness centralities based on the in-degree(_in-\(Cc\)_) and out-degree(_out-\(Cc\)_) are used to measure how many steps are required to access every other node from a given node.