applied sciences  
A Node Differential Privacy-Based Method to Preserve Directed Graphs in Wireless Mobile Networks  
[PERSON] 1,2,3, [PERSON] 1 and [PERSON] 4,*  
Footnote 11: footnot  
original graph while retaining the characteristics of an original graph as much as possible [7]. To overcome the shortcoming of this method, many k-anonymity methods that can resist attacks based on the structure of the graph have been devised, such as (k,l)-anonymity [8], k2-anonymity [9] and k-neighborhood sub-graph anonymity [10]. Clustering-based methods, called generalization methods, usually group nodes and edges into super-nodes and super-edges, which hide the detail of nodes and edges in the graph [11]. Furthermore, the method combining k-anonymity with node clustering is designed, which can provide sufficient privacy preservation while retaining data utility [12]. Compared with the two methods mentioned above, the uncertain graph method, which rejects the uncertainty on the edges of a graph to generate an uncertain graph, can get better data utility than them. Although graph modification can preserve the graph structure data, it is not able to resist attacks based on background knowledge. As a gold-standard notion of privacy that can provide a strict privacy guarantee [13], differential privacy has been adopted to preserve graph structure data [14]. For instance, differential privacy has been extensively applied to preserve various statistical values of the graph, such as the degree distribution [15], frequent graphics patterns [16], and triangle count [17]. In addition, it can also be used to generate a synthetic graph to preserve the original graph. In [18], a synthetic graph is released by using a differential private estimator of the parameters of a special model, which is an exponential family model with the degree sequence as a sufficient statistic. To improve the data utility of a differential private synthetic graph [19], devises a differential private graph generator based on the dK-graph model. Different from graph modification, differential privacy usually employs noise to achieve privacy preservation, which results in insufficient data utility. However, the methods introduced above mainly concentrate on undirected graphs. As a special graph, directed graphs, such as the who-follows-whom social graph on Twitter, not only possess the relations in graphs but also have the direction information. Therefore, it is hard to adopt these methods to preserve directed graphs when it is published or shared. By considering the direction information of edges, a few k-anonymity methods have been designed in [20; 21]. But the k-anonymity method is not able to resist attacks based on background knowledge and only withstand some special attacks, these methods cannot provide sufficient privacy preservation for directed graphs. As a result, it is a great challenge to preserve directed graphs. To solve this problem, we propose a useful method that combines differential privacy with graph modification to preserve directed graphs. In particular, compared with edge differential privacy, node differential privacy can provide stronger privacy preservation. Thus, node differential privacy is used to add noise on degree sequences, and edge modification utilizes noised degree sequences to generate a synthetic directed graph, which provides strong privacy preservation for 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, which is useful to maintain the whole graph structure. In particular, the exponent mechanism is adopted to truncate degree sequences, which can ensure that the minimum noise is added to the degree sequences. Moreover, the ranking micro-aggregation effectively reduces the noise added to the degree sequences. According to the noised degree sequences, the relationship between two nodes is utilized to modify the edges of nodes, which can retain the original graph structure.