# An Edge Correlation Based Differentially Private Network Data Release Method

Authors: Junling Lu; Zhipeng Cai; Xiaoming Wang; Lichen Zhang; Zhuojun Duan
Journal: Security and Communication Networks
 (2017)

---

## Abstract

Differential privacy (DP) provides a rigorous and provable privacy guarantee and assumes adversaries’ arbitrary background knowledge, which makes it distinct from prior work in privacy preserving. However, DP cannot achieve claimed privacy guarantees over datasets with correlated tuples. Aiming to protect whether two individuals have a close relationship in a correlated dataset corresponding to a weighted network, we propose a differentially private network data release method, based on edge correlation, to gain the tradeoff between privacy and utility. Specifically, we first extracted the Edge Profile (PF) of an edge from a graph, which is transformed from a raw correlated dataset. Then, edge correlation is defined based on the PFs of both edges via Jenson-Shannon Divergence (JS-Divergence). Secondly, we transform a raw weighted dataset into an indicated dataset by adopting a weight threshold, to satisfy specific real need and decrease query sensitivity. Furthermore, we proposeϵ-correlated edge differential privacy (CEDP), by combining the correlation analysis and the correlated parameter with traditional DP. Finally, we propose network data release (NDR) algorithm based on the ϵ-CEDP model and discuss its privacy and utility. Extensive experiments over real and synthetic network datasets show the proposed releasing method provides better utilities while maintaining privacy guarantee.


---

## Body

## 1. Introduction

Recently, social networking such as cooperation networks, online/mobile social networks, and software defined vehicular network [1] is becoming increasingly prevalent. Accompanied with the growth of the networks, mass of network data is released for analytical decisions or scientific researches. However, direct publication of these data, including sensitive information, leads to privacy leakage of individuals. For example, whether two individuals in a social network have a close relationship may be expected to be kept a secret. Therefore, privacy concerns have been raised in increasingly emerging technologies [2–9].In general, a dataset corresponding to such a network, usually modeled as a graph, is considered as correlated data; that is, tuples in this dataset are dependent. Clearly, privacy preserving in such correlated settings is more difficult because an adversary can infer the relationship of two individuals from their associated friends. Accordingly, our concern is preventing, whether the relationship of two individuals appears in a network dataset, from being unveiled.Differential privacy (DP), a privacy preserving model originated from statistical database, has currently drawn considerable attentions in research communities [10–17] due to (i) its rigorous and provable privacy guarantee and (ii) its assumption of adversaries’ arbitrary background knowledge. However, DP actually assumes that the tuples in databases are independent [18]. In other words, DP cannot provide claimed privacy guarantees over correlated (nonindependent) data [19]. Therefore, the application of DP over correlated data is a challenge, and how to achieve a differentially private correlated data release method deserves to be further explored.The focus of our work is on hiding the affinity degree of two individuals in a correlated dataset corresponding to a weighted network, that is, protecting whether the affinity degree of two individuals exceeds a given weight threshold, in a differentially private manner. Toward this end, we first transform a weighted network dataset into a corresponding weighted graph and define the correlation of both edges via Jenson-Shannon Divergence (JS-Divergence). For satisfying specific query need in spite of some utility loss, we utilize Threshold Based Transformation (TBT) algorithm to transform a weighted dataset, by adopting a weight threshold, into an indicated dataset, which also decreases query sensitivity. Finally, we present the notion ofϵ-correlated edge differential privacy (CEDP), by combining the correlation analysis and the correlated parameter, that is, the maximal number of correlated tuples, with traditional DP, and design differentially private network data release (NDR) algorithm to obtain better utilities while maintaining DP guarantee. Experimental results over real and synthetic network datasets also show the advantages of the proposed method. The framework of our solution is shown in Figure 1.Figure 1
The framework of our solution.The contributions of our work are as follows.First, we extract the Edge Profile (PF) vectors of edges in a weighted graph corresponding to a network dataset and then define the correlation of both edges via JS-Divergence. The inferred correlation analysis is more reasonable for datasets corresponding to such networks, since the typical Pearson correlation coefficient assumes that sample data follows normal distribution; however, the degree and weight distributions in such networks are often not so.Second, we propose theϵ-CEDP model based on our result of correlation analysis and the introduction of the correlated parameter, which makes DP over correlated datasets applicable and flexible. Furthermore, the NDR algorithm, based on correlated sensitivity and Laplace mechanism, is proposed, which also satisfies ϵ-CEDP and achieves the tradeoff of privacy and utility.Third, we utilize TBT algorithm to transform a raw weighted dataset into an indicated dataset; that is, a weight value is equal to 1 or 0, by adopting a weight threshold, to satisfy specific real need and decrease query sensitivity. Admittedly, some utility loss exists in such transformation. However, many queries in real world only need Boolean values indicated by one and zero instead of accurate numeric answers. Therefore, this solution provides a feasible way for decreasing query sensitivity while maintaining real query need.The rest of this paper is organized as follows. Section2 discusses related literature. Section 3 provides the preliminaries. In Section 4, correlation analysis of both edges in a weighted graph is presented, and the ϵ-CEDP model and sensitivity calculation are proposed. Furthermore, a differentially private NDR algorithm, including TBT algorithm, to obtain the tradeoff between privacy and utility over correlated data is proposed in Section 5. The extensive experiments are illustrated in Section 6. Finally, Section 7 concludes the paper.


## 2. Related Work

Compared with previous works in privacy preserving, DP proposed by Dwork [20] provides a probabilistic formulation, which represents that adversaries learn little from both databases differing in one tuple even if adversaries know about all tuples except the target one. In other words, the inference abilities of adversaries about the presence or absence of a tuple are bounded regardless of adversaries’ knowledge; that is, the presence or absence of a tuple is probabilistically indistinguishable for adversaries.Currently, DP has drawn much attention in privacy preserving work needed in many fields. Wang et al. [10] considered a unified privacy distortion framework, where the distortion is defined to be the expected Hamming distance between the input and output databases, and investigated the relation between three different notions of privacy: identifiability, differential privacy, and mutual-information privacy. To provide personalized recommendation in big data resulting from social networks and maintain user privacy, a cloud-assisted differentially private video recommendation system based on distributed online learning was proposed [11]. The work in [12] proposed a new privacy preserving smart metering scheme for smart grid, which supports data aggregation, differential privacy, fault tolerance, and range-based filtering simultaneously. To et al. [13] introduced a novel privacy-aware framework for spatial crowdsourcing, which enables the participation of workers without compromising their location privacy. Focusing on the privacy protection of sensitive information in body area networks, the authors in [14, 15] proposed different privacy preserving schemes, based on differential privacy model, via a tree structure and dynamic noise thresholds, respectively. The work in [16] proposed a novel differentially private frequent sequence mining algorithm by leveraging a sampling-based candidate pruning technique, which satisfies ϵ-differential privacy and can privately find frequent sequences with high accuracy. In order to protect users’ privacy in ridesharing services, a jointly differentially private scheduling protocol has been proposed [17], which aims to protect riders’ location information and minimize the total additional vehicle mileage in the ridesharing system.However, existing works have found that DP provides weaker privacy guarantee over nonindependent data; that is, DP needs more noise added to the output query result to cancel out the impact of correlations among tuples on privacy guarantee. Undoubtedly, how to analyze correlations among tuples and apply them into DP are desired to be further explored. For example, Kifer and Machanavajjhala [19] first explicitly doubted the privacy guarantee of DP in correlated settings, for example, social networks, and then adopted the subsequently proposed privacy framework, that is, Pufferfish, to formalize and prove that DP assumes independence between tuples [18]. Inspired by the Pufferfish framework, Blowfish privacy [21] was proposed to achieve the tradeoff between privacy and utility using policies specifying secrets and constraints. Similarly, the authors in [22] proposed Bayesian DP to evaluate the level of private information leakage even when data is correlated and prior knowledge is incomplete. The work in [23] regarded the correlation among tuples as complete correlation and multiplied the query sensitivity with the number of correlated tuples in publishing correlated network data, which leaves room for fine-grained correlation analysis in the following work. Aiming to decrease the noise amount, Zhu et al. [24] depicted the correlation between tuples via Pearson correlation coefficient, including complete correlation, partial correlation, and independence. Liu et al. [25] inferred the dependence coefficient, distributed in interval [0,1], to evaluate the probabilistic correlation between two tuples in a more fine-grained manner, thus reducing the query sensitivity which results in less noise. Considering temporal correlations of a moving user’s locations, the work in [26] leveraged a hidden Markov model to establish a location set and proposed a variant of DP to protect location privacy. Wu et al. [27] proposed the definition of correlated differential privacy to evaluate the real privacy level of a single dataset influenced by the other datasets when multiple datasets are correlated. The work in [28] formalized the privacy preservation problem to an optimization problem by modeling the temporal correlations among contexts and further proposed an efficient context-aware privacy preserving algorithm. Cao et al. [29] modeled the temporal correlations using Markov model and investigated the privacy leakage of a traditional DP mechanism under temporal correlations in the context of continuous data release. The work in [30] quantified the location correlation between two users through the similarity measurement of two hidden Markov models and applied differential privacy via private candidate sets to achieve the multiuser location correlation protection.As seen from the above discussions, correlation analysis plays an important role in privacy preserving mechanisms, which directly influences the tradeoff between privacy protection and service utility. Obviously, the more accurate the correlation analysis, the better the balance of both aspects. Therefore, we attribute the underestimated privacy guarantee of DP over correlated data to the lack of data knowledge, and our work starts from data correlation analysis.In this paper, we focus on correlated datasets corresponding to weighted cooperation networks. Different from the existing methods of correlation analysis, for example, simple multiplication in [23], Pearson correlation coefficient in [24], and the maximal information coefficient in [31], we extract the PF vectors of edges in a weighted graph corresponding to a correlated dataset and then define the correlation of both edges via JS-Divergence, which is more accurate and reasonable. Specifically, the work in [23] assumes both tuples are completely correlated; however, our proposed correlation results lie in interval [0,1] representing multiple correlation including complete correlation. In addition, the work in [24] assumes sample data follows normal distribution, while our method is not the case. Also, the maximal information coefficient proposed in [31] satisfies two heuristic properties including generality and equitability, and we will consider it in our future work.


## 3. Preliminaries

### 3.1. Differential Privacy

Differential privacy provides the privacy guarantee for an individual in the probabilistic sense [20]. It is defined as follows.Definition 1 (ϵ-differential privacy).
A randomized mechanismA satisfies ϵ-differential privacy if, for any pair of databases D and D′ differing in only one tuple and for any output S∈OA representing the possible output set of A, (1)Pr⁡AD=S≤exp⁡ϵ·Pr⁡AD′=S,where ϵ is the privacy budget depicting the probabilistic difference between the same outputs of A over D and D′.
Generally, DP is achieved via two mechanisms: Laplace mechanism [32] and exponential mechanism [33]. Both mechanisms include a concept of global sensitivity [20], which reveals DP’s preferable choice of protecting the extreme case.Definition 2 (global sensitivity).
For any query functionf:D→Rd, where D is a dataset and Rd is a d-dimension real-valued vector, the global sensitivity of f is defined as (2)Δf=maxD,D′⁡fD-fD′1, where D and D′ denote any pair of databases differing in only one tuple and ·1 denotes l1 norm.
Laplace mechanism, used in this paper, is formally presented as follows.Theorem 3 (Laplace mechanism).
Given any query functionf:D→Rd, where D is a dataset and Rd is a d-dimension real-valued vector, the global sensitivity Δf of f, and privacy budget ϵ, a randomized mechanism A(3)AD=fD+LaplaceΔfϵprovides the ϵ-differential privacy, where Laplace· denotes Laplace noise.


### 3.2. Weighted Adjacency Matrix

In this paper, we model a correlated dataset as a weighted undirected simple graphG=V,E,W, where V=v1,…,vn is the set of vertices and n=V is the number of vertices, E=eij is the set of edges and eij=vi,vj, vi∈V,  i=1,…,n, vj∈V, j=1,…,n, and W=wij is the set of weights where weight wij corresponds with edge eij. Then, the weighted adjacency matrix Aw of G can be denoted as(4)Aijw=wij,eij∈E0,otherwise, where wij represents the affinity degree between two individuals. Obviously, the weighted adjacency matrix Aijw is symmetric.Example 4.
Suppose a raw weighted datasetDW is listed in Table 1. Then, the corresponding weighted adjacency matrix Aw of DW can be denoted as (5)020000204810040000080053010500000300.Table 1
A raw weighted dataset.
V
i
V
j
w
i
j
1
2
2
2
3
4
2
4
8
2
5
1
4
5
5
4
6
3
Note. Vi and Vj denote two individuals, and weight wij denotes the relation strength between them.


### 3.3. Correlation Metric

Motivated by the entropy in information theory, we adopt JS-Divergence, inferred from Kullback-Leibler Divergence (KL-Divergence) [23], to depict the difference of two distributions, which can be transformed to depict the correlation of two tuples in a correlated dataset.Definition 5 (KL-Divergence).
SupposeP=p1,p2,…,pn and Q=q1,q2,…,qn are the probability distributions of random variables X=x1,x2,…,xn and Y=y1,y2,…,yn; then the KL-Divergence of P and Q is defined as follows: (6)KLDP∥Q=∑i=1npiln⁡piqi.
Here0log⁡0 = 0 is required. Based on KL-Divergence, we can obtain JS-Divergence as follows.Definition 6 (JS-Divergence).
SupposeP=p1,p2,…,pn and Q=q1,q2,…,qn are the probability distributions of random variables X=x1,x2,…,xn and Y=y1,y2,…,yn, and M=1/2P+Q; then the JS-Divergence of P and Q is defined as follows: (7)JSDP∥Q=12KLDP∥M+KLDQ∥M=12∑i=1npiln⁡2pipi+qi+qiln⁡2qipi+qi.


## 3.1. Differential Privacy

Differential privacy provides the privacy guarantee for an individual in the probabilistic sense [20]. It is defined as follows.Definition 1 (ϵ-differential privacy).
A randomized mechanismA satisfies ϵ-differential privacy if, for any pair of databases D and D′ differing in only one tuple and for any output S∈OA representing the possible output set of A, (1)Pr⁡AD=S≤exp⁡ϵ·Pr⁡AD′=S,where ϵ is the privacy budget depicting the probabilistic difference between the same outputs of A over D and D′.
Generally, DP is achieved via two mechanisms: Laplace mechanism [32] and exponential mechanism [33]. Both mechanisms include a concept of global sensitivity [20], which reveals DP’s preferable choice of protecting the extreme case.Definition 2 (global sensitivity).
For any query functionf:D→Rd, where D is a dataset and Rd is a d-dimension real-valued vector, the global sensitivity of f is defined as (2)Δf=maxD,D′⁡fD-fD′1, where D and D′ denote any pair of databases differing in only one tuple and ·1 denotes l1 norm.
Laplace mechanism, used in this paper, is formally presented as follows.Theorem 3 (Laplace mechanism).
Given any query functionf:D→Rd, where D is a dataset and Rd is a d-dimension real-valued vector, the global sensitivity Δf of f, and privacy budget ϵ, a randomized mechanism A(3)AD=fD+LaplaceΔfϵprovides the ϵ-differential privacy, where Laplace· denotes Laplace noise.


## 3.2. Weighted Adjacency Matrix

In this paper, we model a correlated dataset as a weighted undirected simple graphG=V,E,W, where V=v1,…,vn is the set of vertices and n=V is the number of vertices, E=eij is the set of edges and eij=vi,vj, vi∈V,  i=1,…,n, vj∈V, j=1,…,n, and W=wij is the set of weights where weight wij corresponds with edge eij. Then, the weighted adjacency matrix Aw of G can be denoted as(4)Aijw=wij,eij∈E0,otherwise, where wij represents the affinity degree between two individuals. Obviously, the weighted adjacency matrix Aijw is symmetric.Example 4.
Suppose a raw weighted datasetDW is listed in Table 1. Then, the corresponding weighted adjacency matrix Aw of DW can be denoted as (5)020000204810040000080053010500000300.Table 1
A raw weighted dataset.
V
i
V
j
w
i
j
1
2
2
2
3
4
2
4
8
2
5
1
4
5
5
4
6
3
Note. Vi and Vj denote two individuals, and weight wij denotes the relation strength between them.


## 3.3. Correlation Metric

Motivated by the entropy in information theory, we adopt JS-Divergence, inferred from Kullback-Leibler Divergence (KL-Divergence) [23], to depict the difference of two distributions, which can be transformed to depict the correlation of two tuples in a correlated dataset.Definition 5 (KL-Divergence).
SupposeP=p1,p2,…,pn and Q=q1,q2,…,qn are the probability distributions of random variables X=x1,x2,…,xn and Y=y1,y2,…,yn; then the KL-Divergence of P and Q is defined as follows: (6)KLDP∥Q=∑i=1npiln⁡piqi.
Here0log⁡0 = 0 is required. Based on KL-Divergence, we can obtain JS-Divergence as follows.Definition 6 (JS-Divergence).
SupposeP=p1,p2,…,pn and Q=q1,q2,…,qn are the probability distributions of random variables X=x1,x2,…,xn and Y=y1,y2,…,yn, and M=1/2P+Q; then the JS-Divergence of P and Q is defined as follows: (7)JSDP∥Q=12KLDP∥M+KLDQ∥M=12∑i=1npiln⁡2pipi+qi+qiln⁡2qipi+qi.


## 4. Correlation Analysis of Weighted Edges

In this section, we first discuss how to define the correlation of both edges in a weighted graph corresponding to a network dataset and then introduce why and how we conduct dataset transformation based on a given weight threshold. Finally, we define theϵ-CEDP model and calculate the correlated sensitivity for smaller added noise.


### 4.1. Correlation Definition

For achieving the correlation of tuples in a raw weighted datasetDW, we first obtain a weighted graph G, whose weighted adjacency matrix is denoted by Aw. Then, the correlation problem is changed to seeking the correlation of edges in G. To this end, we first describe the PF vector of a weighted edge from the perspectives of relational strength and network structure and then define the correlation of both edges via JS-Divergence instead of Pearson correlation coefficient.For a weighted edgeeij, suppose Vi=v∣v,vi∈E,v≠vi represents the set of vertices connected with vi and Vj=v∣v,vj∈E,v≠vj represents the set of vertices connected with vj; we extract the PF vector of eij, denoted by PFeij, from the perspectives of relational strength and network structure simultaneously. Specifically, we obtain wij/maxeij∈E⁡wij∈0,1 from the global weights of all edges. In addition, we get wij/∑v∈Viwiv∈0,1 and wij/∑v∈Vjwjv∈0,1 from the local weights of edge eij. On the other hand, similar to the representation of relational strength, Degvi/maxv∈V⁡Degv∈0,1 and Degvj/maxv∈V⁡Degv∈0,1 are constructed, by introducing the node degree Deg·, to depict the global active degree for both vertices of edge eij. Also, Vi∩Vj/Vi∪Vj∈0,1 is adopted, via the set similarity, to depict the ratio of the number of common vertices connecting vi and vj to that of Vi and Vj. Meanwhile, Degvi/∑v∈ViDegv∈0,1 and Degvj/∑v∈VjDegv∈0,1 are used to depict the local active degree for both vertices of edge eij. Combining the above factors, we obtain PFeij as follows:(8)PFeij=wijmaxeij∈E⁡wij,wij∑v∈Viwiv,wij∑v∈Vjwjv,Degvimaxv∈V⁡Degv,Degvjmaxv∈V⁡Degv,Vi∩VjVi∪Vj,Degvi∑v∈ViDegv,Degvj∑v∈VjDegv.Similarly, for any other edgeemn, according to (8), we define PFemn as follows:(9)PFemn=wmnmaxemn∈E⁡wmn,wmn∑v∈Vmwmv,wmn∑v∈Vnwnv,Degvmmaxv∈V⁡Degv,Degvnmaxv∈V⁡Degv,Vm∩VnVm∪Vn,Degvm∑v∈VmDegv,Degvn∑v∈VnDegv.Note that Pearson correlation coefficient assumes that sample data follows normal distribution. However, in social networks, the weight and degree distributions do not follow such distribution, which is also verified by our experiments shown in Figure2, where geom and out are the abbreviations of geom.net [34–36] and out.moreno_lesmis_lesmis [37–39] for simplicity. Specifically, i geom.net is the authors collaboration network in Computational Geometry based on the file geombib.bib, and the reduced simple network contains 7343 vertices and 11898 edges. Two authors are linked with an edge, iff they wrote a common work. The value of an edge is the number of common works. ii out.moreno_lesmis_lesmis is the characters cooccurrences network in Victor Hugo’s novel “Les Misérables,” and it contains 77 vertices and 254 edges. A node represents a character and an edge between two nodes shows that these two characters appeared in the same chapter of the book. The weight of each link indicates how often such a coappearance occurred.Figure 2
Degree distribution and weight one on network data.
(a)
Degree distribution on geom
(b)
Weight distribution on geom
(c)
Degree distribution on out
(d)
Weight distribution on outSince our constructed PF vectors of edges do not satisfy the assumption of normal distribution, we adopt JS-Divergence, instead of Pearson correlation coefficient, to measure the CORrelation (COR) of any two edgeseij, emn in a weighted graph. To this end, we normalize PFeij and PFemn as PNeij and PNemn, which are two probability distributions. Therefore, we have(10)PNeij=PFeijSij, where Sij=wij/maxeij∈E⁡wij+wij/∑v∈Viwiv+wij/∑v∈Vjwjv + Degvi/maxv∈V⁡Degv + Degvj/maxv∈V⁡Degv + Vi∩Vj/Vi∪Vj+Degvi/∑v∈ViDegv+Degvj/∑v∈VjDegv and(11)PNemn=PFemnSmn, where Smn=wmn/maxemn∈E⁡(wmn)⁡+wmn/∑v∈Vmwmv+wmn/∑v∈Vnwnv + Deg(vm)/maxv∈V⁡(Deg(v)) + Deg(vn)/maxv∈V⁡(Deg(v)) + Vm∩Vn/Vm∪Vn+Deg(vm)/∑v∈VmDegv+Deg(vn)/∑v∈VnDegv.Meanwhile, we consider the distance of both edges as follows.Definition 7 (edge distance).
Supposeeij=vi,vj and emn=vm,vn are two edges in graph G, dv1,v2 denotes the length of the shortest path between nodes v1 and v2, and I is the index of the smallest value in vector dvi,vm,dvi,vn,dvj,vm,dvj,vn; then the distance of eij and emn is defined as follows:(12)diseij,emn=dvi,vm+dvj,vn,I=1dvi,vn+dvj,vm,I=2dvj,vm+dvi,vn,I=3dvj,vn+dvi,vm,I=4.
Specifically, we first calculate the distances includingdvi,vm, dvi,vn, dvj,vm, and dvj,vn and then determine the smallest one among these distances and its index I, complete the calculation of the distance of another pair of nodes, and finally obtain the distance of two edges eij and emn.Based on Definitions6 and 7, we define the CORrelation (COR) of two probability distributions via JS-Divergence as follows.Definition 8 (CORrelation).
SupposeP=p1,p2,…,pn and Q=q1,q2,…,qn are the probability distributions of random variables X=x1,x2,…,xn and Y=y1,y2,…,yn; then the CORrelation of P and Q is defined as follows:(13)CORP,Q=1-JSDP∥Q1+diseij,emn.
According to (10)–(13) and Definition 6, we adopt the normalized PN vectors of edges eij, emn to measure their correlation as(14)COReij,emn=11+diseij,emn1-12∑k=18PNeijkln⁡PNeijkPNMk-12∑k=18PNemnkln⁡PNemnkPNMk, where PN·k denotes the k element of vector PN· and(15)PNMk=12PNeijk+PNemnk.Substituting (15) into (14), we obtain(16)COReij,emn=11+diseij,emn1-12∑k=18PNeijkln⁡2PNeijkPNeijk+PNemnk-12∑k=18PNemnkln⁡2PNemnkPNeijk+PNemnk.In our opinion, the proposed correlation definition, extracted from two aspects of relational strength and network structure, is more reasonable. The rationale is (i) graph models, commonly abstracted from networks, reflect inherent dependent relations of individuals, which naturally form edge correlations and (ii) the weights of edges in weighted graphs describe the affinity degree of individuals’ relations, which also influence the variances of edge correlations.Example 9.
Takee24 and e25 in DW as an example to demonstrate the calculation of CORe24,e25. According to (8) and (9), we have (17)PFe24=88,815,816,44,34,16,47,37,PFe25=18,115,16,44,24,15,47,27.
Furthermore, according to (10) and (11), we get (18)PNe24=0.2020,0.1077,0.1010,0.2020,0.1515,0.0337,0.1154,0.0866,(19)PNe25=0.0429,0.0229,0.0572,0.3430,0.1715,0.0686,0.1960,0.0980.
Finally, according to (16), we obtain (20)CORe24,e25=0.4679.


### 4.2. Dataset Transformation

We consider some real world situations that do not need exact query answers. For example, people sometimes only want to learn about whether two individuals have an intimate relationship or not, rather than the specific number of communication or cooperation. So the privacy concern at this time is to avoid the leakage of close relationship, that is, yes or no. Therefore, the first thing we focus on is to transform a weighted datasetDW to an indicated dataset DI, based on a given weight threshold T. In other words, we consider replacing query “Select SUM(weight) from DW where wij>T” with query “Select COUNT(∗) from DW where wij>T”, which satisfies some specific situations and decreases the query sensitivity simultaneously. Note that this method aims to avoid the leakage of whether an edge satisfying the given threshold condition exists and not to avoid the weights of edges satisfying the one exposed. In our opinion, this solution is reasonable and suitable for achieving privacy protection via DP in spite of some utility loss.To this end, we propose the TBT algorithm to modify raw weight valueswij in DW as an indicated value; that is, wij=1 if wij>T; otherwise, wij=0, thus transforming DW to DI. The TBT algorithm is presented in Algorithm 1.Algorithm 1:TBT algorithm.
Input: Weighted dataset DW, weight threshold T.
Output: Indicated dataset DI.
(1) for (Each tuple (i,j)∈DW) do
(2)if (wij>T) then
(3)wij = 1;
(4)else
(5)wij = 0;
(6)end if
(7)end for
(8) return  DI with indicated values.


### 4.3. Correlated Edge Differential Privacy

As discussed above, we only consider the situations: the query answers responding to a correlated weighted data are yes or no, which indicates whether two individuals have close relationship. That is, the privacy concern herein is to avoid the leakage of whether there is a close relationship between two individuals, in a weighted dataset whose at mostz tuples are correlated, where z is the correlated parameter. To this end, we first define correlated neighboring databases as follows.Definition 10 (correlated neighboring databases).
Any pair of databasesDCOR,z and DCOR,z′ are correlated neighboring databases, if the weight change of a tuple in DCOR,z results in the weight changes of at most z-1 other correlated tuples in D′ based on the correlation COR·,· of both tuples.Note that the neighboring databases in Definition10 are described by two parameters: the correlation COR·,· aforementioned and the correlated parameter z. Specifically, we have the following.(i) Based on JS-Divergence, we have the following conclusion about the correlationCOR·,·.Theorem 11.
For any two edgeseij and emn in the weighted graph G corresponding to a network dataset DW, 0≤COReij,emn≤1 holds.Proof.
For the ease of exposition, we denote the last two items in the numerator of (16) as follows.(21)JSDeij∥emn=12∑k=18PNeijkln⁡2PNeijkPNeijk+PNemnk+PNemnkln⁡2PNemnkPNeijk+PNemnk.
SincePN· denotes a probability distribution, we have(22)∑k=18PNeijk=1,∑k=18PNemnk=1;we consider two cases separately.
Case 1 (COReij,emn≤1). Since ln⁡x≤x-1 when x>0, we have(23)∑k=18PNeijkln⁡2PNeijkPNeijk+PNemnk≤∑k=18PNeijk2PNeijkPNeijk+PNemnk-1=∑k=18PNeijkPNeijk-PNemnkPNeijk+PNemnk≤∑k=18PNeijk.
Substituting (22) into (23), we have(24)∑k=18PNeijkln⁡2PNeijkPNeijk+PNemnk≤1.
Similarly, we obtain(25)∑k=18PNemnkln⁡2PNemnkPNeijk+PNemnk≤1.
Combining (21), (24), and (25), we have(26)JSDeij∥emn≤1.
Case 2(COReij,emn≥0).Since ln⁡x≥1-1/x when x>0, we have(27)∑k=18PNeijkln⁡2PNeijkPNeijk+PNemnk≥∑k=18PNeijk1-PNeijk+PNemnk2PNeijk=∑k=18PNeijk-PNemnk2.Similarly, we obtain(28)∑k=18PNemnkln⁡2PNemnkPNeijk+PNemnk≥∑k=18PNemnk-PNeijk2.Combining (21), (27), and (28), we have(29)JSDeij∥emn≥0.Combining (26) with (29), then we have(30)0≤JSDeij∥emn≤1.
Note thatdiseij,emn≥0 due to (12). Finally, according to (16) and (30), we have (31)0≤COReij,emn≤1.Clearly,COReij,emn=0 denotes eij is independent of emn; that is, the corresponding tuples in a dataset are independent. COReij,emn=1 denotes eij is fully dependent to emn; that is, the corresponding tuples in a dataset are fully correlated. 0<COReij,emn<1 denotes eij is partially dependent on emn; that is, the corresponding tuples in a dataset are partially correlated.(ii) Similar to [23–25], we introduce the correlated parameter z representing that there are at most z correlated tuples in a dataset. In other words, a tuple is correlated with at most z-1 other tuples; that is, an edge in a graph is correlated with at most z-1 other edges. Obviously, z=1 represents the independent case of tuples in a dataset, z=n represents the fully correlated case of tuples in a dataset, and 1<z<n represents the partially correlated case of tuples in a dataset. Therefore, the variance of z increases the flexibility of Definition 10.Furthermore, we define theϵ-CEDP model as follows.Definition 12 (ϵ-correlated edge differential privacy).
A randomized mechanismM satisfies ϵ-differential privacy if, for any neighboring databases DCOR,z and DCOR,z′ and for any output S∈OM representing the possible output set of M, (32)Pr⁡MDCOR,z=S≤exp⁡ϵ·Pr⁡MDCOR,z′=S, where ϵ is the privacy budget depicting the probabilistic difference between the same outputs of M over DCOR,z and DCOR,z′ and COR·,· and z are the correlation of two tuples and the correlated parameter representing the maximal number of correlated tuples, respectively.


### 4.4. Sensitivity Calculation

After transforming weighted datasetDW to indicated dataset DI, we add Laplace noise to query answers based on the ϵ-CEDP model. Laplace noise is determined by two factors: privacy budget ϵ and the global sensitivity of a query, and the latter refers to the maximal change of query result due to the modification of only one tuple. Here, for a query f, assume the global sensitivity of f, resulting from the change of tuple tj, in independent settings is Δfj. Clearly, Δfj=1. However, for dataset DI with n tuples where at most z tuples are correlated, the query sensitivity resulted from modifying tuple ti, called Edge Sensitivity denoted by ESi, is more complex. Specifically, (i) if CORti,tj=0, that is, z=1, denoting the independent case, ESi=1, (ii) if CORti,tj=1 and 2≤z≤n, denoting the fully correlated case, ESi=z, and (iii) if 0<COReij,emn<1 and 2≤z≤n, denoting the partially correlated case, ESi is defined as follows. (33)ESi=∑j=1nCORti,tjΔfj.Since the change of a tuple only affects at most otherz-1 correlated tuples, ESi can be rewritten as (34)ESi=∑j=1zCORti,tjΔfj.Finally, we have the correlated sensitivity denoted by CS, that is, the maximalESi in dataset DI, as follows:(35)CS=maxi∈DI⁡ESi.Note that the CS is also suitable for the independent and fully correlated cases. Based on the CS, we can achieveϵ-CEDP, which is shown as follows.Theorem 13.
Given any query functionf:DCOR,z→Rd, where DCOR,z is a correlated dataset with the correlation definition COR·,· and the correlated parameter z and Rd is a d-dimension real-valued vector, the correlated sensitivity CS of f, and privacy budget ϵ, a randomized mechanism M, (36)MDCOR,z=fDCOR,z+LaplaceCSϵ, provides ϵ-CEDP, where Laplace· denotes Laplace noise.Proof.
(37)
Pr
⁡
M
D
C
O
R
,
z
=
S
Pr
⁡
M
D
C
O
R
,
z
′
=
S
=
exp
⁡
-
ϵ
M
D
C
O
R
,
z
-
f
D
C
O
R
,
z
/
C
S
exp
⁡
-
ϵ
M
D
C
O
R
,
z
′
-
f
D
C
O
R
,
z
′
/
C
S
≤
exp
⁡
ϵ
f
D
C
O
R
,
z
-
f
D
C
O
R
,
z
′
C
S
.
According to (35), the following holds:(38)fDCOR,z-fDCOR,z′CS≤1.
Finally, combining (37) with (38), we have (39)Pr⁡MDCOR,z=SPr⁡MDCOR,z′=S≤exp⁡ϵ.For indicated datasetDI with weight wij∈0,1 and the correlated parameter z, we can easily infer the global sensitivity is equal to z. Due to 0≤COR·,·≤1, we have CS<z. Therefore, CS is less than the global sensitivity. In other words, added noise via CS is less than that via the global sensitivity; hence the utility of the mechanism M based on CS is better.


## 4.1. Correlation Definition

For achieving the correlation of tuples in a raw weighted datasetDW, we first obtain a weighted graph G, whose weighted adjacency matrix is denoted by Aw. Then, the correlation problem is changed to seeking the correlation of edges in G. To this end, we first describe the PF vector of a weighted edge from the perspectives of relational strength and network structure and then define the correlation of both edges via JS-Divergence instead of Pearson correlation coefficient.For a weighted edgeeij, suppose Vi=v∣v,vi∈E,v≠vi represents the set of vertices connected with vi and Vj=v∣v,vj∈E,v≠vj represents the set of vertices connected with vj; we extract the PF vector of eij, denoted by PFeij, from the perspectives of relational strength and network structure simultaneously. Specifically, we obtain wij/maxeij∈E⁡wij∈0,1 from the global weights of all edges. In addition, we get wij/∑v∈Viwiv∈0,1 and wij/∑v∈Vjwjv∈0,1 from the local weights of edge eij. On the other hand, similar to the representation of relational strength, Degvi/maxv∈V⁡Degv∈0,1 and Degvj/maxv∈V⁡Degv∈0,1 are constructed, by introducing the node degree Deg·, to depict the global active degree for both vertices of edge eij. Also, Vi∩Vj/Vi∪Vj∈0,1 is adopted, via the set similarity, to depict the ratio of the number of common vertices connecting vi and vj to that of Vi and Vj. Meanwhile, Degvi/∑v∈ViDegv∈0,1 and Degvj/∑v∈VjDegv∈0,1 are used to depict the local active degree for both vertices of edge eij. Combining the above factors, we obtain PFeij as follows:(8)PFeij=wijmaxeij∈E⁡wij,wij∑v∈Viwiv,wij∑v∈Vjwjv,Degvimaxv∈V⁡Degv,Degvjmaxv∈V⁡Degv,Vi∩VjVi∪Vj,Degvi∑v∈ViDegv,Degvj∑v∈VjDegv.Similarly, for any other edgeemn, according to (8), we define PFemn as follows:(9)PFemn=wmnmaxemn∈E⁡wmn,wmn∑v∈Vmwmv,wmn∑v∈Vnwnv,Degvmmaxv∈V⁡Degv,Degvnmaxv∈V⁡Degv,Vm∩VnVm∪Vn,Degvm∑v∈VmDegv,Degvn∑v∈VnDegv.Note that Pearson correlation coefficient assumes that sample data follows normal distribution. However, in social networks, the weight and degree distributions do not follow such distribution, which is also verified by our experiments shown in Figure2, where geom and out are the abbreviations of geom.net [34–36] and out.moreno_lesmis_lesmis [37–39] for simplicity. Specifically, i geom.net is the authors collaboration network in Computational Geometry based on the file geombib.bib, and the reduced simple network contains 7343 vertices and 11898 edges. Two authors are linked with an edge, iff they wrote a common work. The value of an edge is the number of common works. ii out.moreno_lesmis_lesmis is the characters cooccurrences network in Victor Hugo’s novel “Les Misérables,” and it contains 77 vertices and 254 edges. A node represents a character and an edge between two nodes shows that these two characters appeared in the same chapter of the book. The weight of each link indicates how often such a coappearance occurred.Figure 2
Degree distribution and weight one on network data.
(a)
Degree distribution on geom
(b)
Weight distribution on geom
(c)
Degree distribution on out
(d)
Weight distribution on outSince our constructed PF vectors of edges do not satisfy the assumption of normal distribution, we adopt JS-Divergence, instead of Pearson correlation coefficient, to measure the CORrelation (COR) of any two edgeseij, emn in a weighted graph. To this end, we normalize PFeij and PFemn as PNeij and PNemn, which are two probability distributions. Therefore, we have(10)PNeij=PFeijSij, where Sij=wij/maxeij∈E⁡wij+wij/∑v∈Viwiv+wij/∑v∈Vjwjv + Degvi/maxv∈V⁡Degv + Degvj/maxv∈V⁡Degv + Vi∩Vj/Vi∪Vj+Degvi/∑v∈ViDegv+Degvj/∑v∈VjDegv and(11)PNemn=PFemnSmn, where Smn=wmn/maxemn∈E⁡(wmn)⁡+wmn/∑v∈Vmwmv+wmn/∑v∈Vnwnv + Deg(vm)/maxv∈V⁡(Deg(v)) + Deg(vn)/maxv∈V⁡(Deg(v)) + Vm∩Vn/Vm∪Vn+Deg(vm)/∑v∈VmDegv+Deg(vn)/∑v∈VnDegv.Meanwhile, we consider the distance of both edges as follows.Definition 7 (edge distance).
Supposeeij=vi,vj and emn=vm,vn are two edges in graph G, dv1,v2 denotes the length of the shortest path between nodes v1 and v2, and I is the index of the smallest value in vector dvi,vm,dvi,vn,dvj,vm,dvj,vn; then the distance of eij and emn is defined as follows:(12)diseij,emn=dvi,vm+dvj,vn,I=1dvi,vn+dvj,vm,I=2dvj,vm+dvi,vn,I=3dvj,vn+dvi,vm,I=4.
Specifically, we first calculate the distances includingdvi,vm, dvi,vn, dvj,vm, and dvj,vn and then determine the smallest one among these distances and its index I, complete the calculation of the distance of another pair of nodes, and finally obtain the distance of two edges eij and emn.Based on Definitions6 and 7, we define the CORrelation (COR) of two probability distributions via JS-Divergence as follows.Definition 8 (CORrelation).
SupposeP=p1,p2,…,pn and Q=q1,q2,…,qn are the probability distributions of random variables X=x1,x2,…,xn and Y=y1,y2,…,yn; then the CORrelation of P and Q is defined as follows:(13)CORP,Q=1-JSDP∥Q1+diseij,emn.
According to (10)–(13) and Definition 6, we adopt the normalized PN vectors of edges eij, emn to measure their correlation as(14)COReij,emn=11+diseij,emn1-12∑k=18PNeijkln⁡PNeijkPNMk-12∑k=18PNemnkln⁡PNemnkPNMk, where PN·k denotes the k element of vector PN· and(15)PNMk=12PNeijk+PNemnk.Substituting (15) into (14), we obtain(16)COReij,emn=11+diseij,emn1-12∑k=18PNeijkln⁡2PNeijkPNeijk+PNemnk-12∑k=18PNemnkln⁡2PNemnkPNeijk+PNemnk.In our opinion, the proposed correlation definition, extracted from two aspects of relational strength and network structure, is more reasonable. The rationale is (i) graph models, commonly abstracted from networks, reflect inherent dependent relations of individuals, which naturally form edge correlations and (ii) the weights of edges in weighted graphs describe the affinity degree of individuals’ relations, which also influence the variances of edge correlations.Example 9.
Takee24 and e25 in DW as an example to demonstrate the calculation of CORe24,e25. According to (8) and (9), we have (17)PFe24=88,815,816,44,34,16,47,37,PFe25=18,115,16,44,24,15,47,27.
Furthermore, according to (10) and (11), we get (18)PNe24=0.2020,0.1077,0.1010,0.2020,0.1515,0.0337,0.1154,0.0866,(19)PNe25=0.0429,0.0229,0.0572,0.3430,0.1715,0.0686,0.1960,0.0980.
Finally, according to (16), we obtain (20)CORe24,e25=0.4679.


## 4.2. Dataset Transformation

We consider some real world situations that do not need exact query answers. For example, people sometimes only want to learn about whether two individuals have an intimate relationship or not, rather than the specific number of communication or cooperation. So the privacy concern at this time is to avoid the leakage of close relationship, that is, yes or no. Therefore, the first thing we focus on is to transform a weighted datasetDW to an indicated dataset DI, based on a given weight threshold T. In other words, we consider replacing query “Select SUM(weight) from DW where wij>T” with query “Select COUNT(∗) from DW where wij>T”, which satisfies some specific situations and decreases the query sensitivity simultaneously. Note that this method aims to avoid the leakage of whether an edge satisfying the given threshold condition exists and not to avoid the weights of edges satisfying the one exposed. In our opinion, this solution is reasonable and suitable for achieving privacy protection via DP in spite of some utility loss.To this end, we propose the TBT algorithm to modify raw weight valueswij in DW as an indicated value; that is, wij=1 if wij>T; otherwise, wij=0, thus transforming DW to DI. The TBT algorithm is presented in Algorithm 1.Algorithm 1:TBT algorithm.
Input: Weighted dataset DW, weight threshold T.
Output: Indicated dataset DI.
(1) for (Each tuple (i,j)∈DW) do
(2)if (wij>T) then
(3)wij = 1;
(4)else
(5)wij = 0;
(6)end if
(7)end for
(8) return  DI with indicated values.


## 4.3. Correlated Edge Differential Privacy

As discussed above, we only consider the situations: the query answers responding to a correlated weighted data are yes or no, which indicates whether two individuals have close relationship. That is, the privacy concern herein is to avoid the leakage of whether there is a close relationship between two individuals, in a weighted dataset whose at mostz tuples are correlated, where z is the correlated parameter. To this end, we first define correlated neighboring databases as follows.Definition 10 (correlated neighboring databases).
Any pair of databasesDCOR,z and DCOR,z′ are correlated neighboring databases, if the weight change of a tuple in DCOR,z results in the weight changes of at most z-1 other correlated tuples in D′ based on the correlation COR·,· of both tuples.Note that the neighboring databases in Definition10 are described by two parameters: the correlation COR·,· aforementioned and the correlated parameter z. Specifically, we have the following.(i) Based on JS-Divergence, we have the following conclusion about the correlationCOR·,·.Theorem 11.
For any two edgeseij and emn in the weighted graph G corresponding to a network dataset DW, 0≤COReij,emn≤1 holds.Proof.
For the ease of exposition, we denote the last two items in the numerator of (16) as follows.(21)JSDeij∥emn=12∑k=18PNeijkln⁡2PNeijkPNeijk+PNemnk+PNemnkln⁡2PNemnkPNeijk+PNemnk.
SincePN· denotes a probability distribution, we have(22)∑k=18PNeijk=1,∑k=18PNemnk=1;we consider two cases separately.
Case 1 (COReij,emn≤1). Since ln⁡x≤x-1 when x>0, we have(23)∑k=18PNeijkln⁡2PNeijkPNeijk+PNemnk≤∑k=18PNeijk2PNeijkPNeijk+PNemnk-1=∑k=18PNeijkPNeijk-PNemnkPNeijk+PNemnk≤∑k=18PNeijk.
Substituting (22) into (23), we have(24)∑k=18PNeijkln⁡2PNeijkPNeijk+PNemnk≤1.
Similarly, we obtain(25)∑k=18PNemnkln⁡2PNemnkPNeijk+PNemnk≤1.
Combining (21), (24), and (25), we have(26)JSDeij∥emn≤1.
Case 2(COReij,emn≥0).Since ln⁡x≥1-1/x when x>0, we have(27)∑k=18PNeijkln⁡2PNeijkPNeijk+PNemnk≥∑k=18PNeijk1-PNeijk+PNemnk2PNeijk=∑k=18PNeijk-PNemnk2.Similarly, we obtain(28)∑k=18PNemnkln⁡2PNemnkPNeijk+PNemnk≥∑k=18PNemnk-PNeijk2.Combining (21), (27), and (28), we have(29)JSDeij∥emn≥0.Combining (26) with (29), then we have(30)0≤JSDeij∥emn≤1.
Note thatdiseij,emn≥0 due to (12). Finally, according to (16) and (30), we have (31)0≤COReij,emn≤1.Clearly,COReij,emn=0 denotes eij is independent of emn; that is, the corresponding tuples in a dataset are independent. COReij,emn=1 denotes eij is fully dependent to emn; that is, the corresponding tuples in a dataset are fully correlated. 0<COReij,emn<1 denotes eij is partially dependent on emn; that is, the corresponding tuples in a dataset are partially correlated.(ii) Similar to [23–25], we introduce the correlated parameter z representing that there are at most z correlated tuples in a dataset. In other words, a tuple is correlated with at most z-1 other tuples; that is, an edge in a graph is correlated with at most z-1 other edges. Obviously, z=1 represents the independent case of tuples in a dataset, z=n represents the fully correlated case of tuples in a dataset, and 1<z<n represents the partially correlated case of tuples in a dataset. Therefore, the variance of z increases the flexibility of Definition 10.Furthermore, we define theϵ-CEDP model as follows.Definition 12 (ϵ-correlated edge differential privacy).
A randomized mechanismM satisfies ϵ-differential privacy if, for any neighboring databases DCOR,z and DCOR,z′ and for any output S∈OM representing the possible output set of M, (32)Pr⁡MDCOR,z=S≤exp⁡ϵ·Pr⁡MDCOR,z′=S, where ϵ is the privacy budget depicting the probabilistic difference between the same outputs of M over DCOR,z and DCOR,z′ and COR·,· and z are the correlation of two tuples and the correlated parameter representing the maximal number of correlated tuples, respectively.


## 4.4. Sensitivity Calculation

After transforming weighted datasetDW to indicated dataset DI, we add Laplace noise to query answers based on the ϵ-CEDP model. Laplace noise is determined by two factors: privacy budget ϵ and the global sensitivity of a query, and the latter refers to the maximal change of query result due to the modification of only one tuple. Here, for a query f, assume the global sensitivity of f, resulting from the change of tuple tj, in independent settings is Δfj. Clearly, Δfj=1. However, for dataset DI with n tuples where at most z tuples are correlated, the query sensitivity resulted from modifying tuple ti, called Edge Sensitivity denoted by ESi, is more complex. Specifically, (i) if CORti,tj=0, that is, z=1, denoting the independent case, ESi=1, (ii) if CORti,tj=1 and 2≤z≤n, denoting the fully correlated case, ESi=z, and (iii) if 0<COReij,emn<1 and 2≤z≤n, denoting the partially correlated case, ESi is defined as follows. (33)ESi=∑j=1nCORti,tjΔfj.Since the change of a tuple only affects at most otherz-1 correlated tuples, ESi can be rewritten as (34)ESi=∑j=1zCORti,tjΔfj.Finally, we have the correlated sensitivity denoted by CS, that is, the maximalESi in dataset DI, as follows:(35)CS=maxi∈DI⁡ESi.Note that the CS is also suitable for the independent and fully correlated cases. Based on the CS, we can achieveϵ-CEDP, which is shown as follows.Theorem 13.
Given any query functionf:DCOR,z→Rd, where DCOR,z is a correlated dataset with the correlation definition COR·,· and the correlated parameter z and Rd is a d-dimension real-valued vector, the correlated sensitivity CS of f, and privacy budget ϵ, a randomized mechanism M, (36)MDCOR,z=fDCOR,z+LaplaceCSϵ, provides ϵ-CEDP, where Laplace· denotes Laplace noise.Proof.
(37)
Pr
⁡
M
D
C
O
R
,
z
=
S
Pr
⁡
M
D
C
O
R
,
z
′
=
S
=
exp
⁡
-
ϵ
M
D
C
O
R
,
z
-
f
D
C
O
R
,
z
/
C
S
exp
⁡
-
ϵ
M
D
C
O
R
,
z
′
-
f
D
C
O
R
,
z
′
/
C
S
≤
exp
⁡
ϵ
f
D
C
O
R
,
z
-
f
D
C
O
R
,
z
′
C
S
.
According to (35), the following holds:(38)fDCOR,z-fDCOR,z′CS≤1.
Finally, combining (37) with (38), we have (39)Pr⁡MDCOR,z=SPr⁡MDCOR,z′=S≤exp⁡ϵ.For indicated datasetDI with weight wij∈0,1 and the correlated parameter z, we can easily infer the global sensitivity is equal to z. Due to 0≤COR·,·≤1, we have CS<z. Therefore, CS is less than the global sensitivity. In other words, added noise via CS is less than that via the global sensitivity; hence the utility of the mechanism M based on CS is better.


## 5. Network Data Release Method

Based on indicated datasetDI and the CS discussed in Section 4, we proposed a network data release method in special cases, which achieves the ϵ-CEDP model. Furthermore, the theoretical analysis of privacy and utility is elaborated.


### 5.1. NDR Algorithm

The goal of NDR algorithm is to achieve the tradeoff between privacy and utility under correlated settings. To this end, three phases are taken into account: (i) for achieving the correlation of two tuples inDW, we transform dataset DW into the corresponding graph and calculate the correlation COR·,· of both edges via the JS-Divergence, (ii) based on a given weight threshold T, we convert DW into DI via TBT algorithm. In other words, the sensitivity in independent settings is 1, irrelevant to the weights. Furthermore, we implement the calculation of CS, and (iii) combining the affordable privacy budget ϵ with CS, we calculate the added Laplace noise and finally obtain the noisy query result MDI for query f in query set Q. The NDR algorithm is presented in Algorithm 2.Algorithm 2:NDR algorithm.
Input: Original dataset DW, privacy budget ϵ, correlated parameter z, threshold T and query set Q.
Output: Noisy query result M(DW).
(1) Calculate the correlation COR(⋅,⋅) of any two edges in DW according to Eq. (16);
(2) Call Algorithm TBT(DW, T), return DI;
(3) Calculate the correlated sensitivity CS according to Eq. (35);
(4) for (Each f∈Q) do
(5)M(DI)=f(DI)+LaplaceCSϵ;
(6) end for
(7) return Noisy query result M(DI) as M(DW).


### 5.2. Utility Analysis

Clearly, NDR algorithm satisfies theϵ-CEDP model. To conduct utility analysis, we adopt the α,δ-useful definition in [40] to depict the utility of NDR as follows.Definition 14.
A mechanism NDR isα,δ-useful for a query f in all queries Q, if, with probability at least 1-δ, for any query f and dataset D, NDR satisfies maxf∈Q⁡NDRD-fD≤α.Based on Definition14, we obtain the following utility analysis.Theorem 15.
For any queryf∈Q and dataset D, a mechanism NDR satisfies α,δ-useful if NDR can obtain maxf∈Q⁡NDRD-fD≤α with at least probability 1-δ when δ≥exp⁡-ϵα/CS.Proof.
By Definition14, we have(40)Pr⁡maxf∈Q⁡NDRD-fD≤α=Pr⁡maxf∈Q⁡LaplaceCSϵ≤α=∫-ααϵ2CSexp⁡-ϵxCSdx=∫0αϵCSexp⁡-ϵxCSdx=1-exp⁡-ϵαCS.
Ifδ≥exp⁡-ϵα/CS, then the following holds:(41)1-exp⁡-ϵαCS≤1-δ.
According to (40) and (41), we obtain (42)Pr⁡maxf∈Q⁡NDRD-fD≤α≤1-δ.
Therefore, mechanism NDR satisfiesα,δ-useful.


## 5.1. NDR Algorithm

The goal of NDR algorithm is to achieve the tradeoff between privacy and utility under correlated settings. To this end, three phases are taken into account: (i) for achieving the correlation of two tuples inDW, we transform dataset DW into the corresponding graph and calculate the correlation COR·,· of both edges via the JS-Divergence, (ii) based on a given weight threshold T, we convert DW into DI via TBT algorithm. In other words, the sensitivity in independent settings is 1, irrelevant to the weights. Furthermore, we implement the calculation of CS, and (iii) combining the affordable privacy budget ϵ with CS, we calculate the added Laplace noise and finally obtain the noisy query result MDI for query f in query set Q. The NDR algorithm is presented in Algorithm 2.Algorithm 2:NDR algorithm.
Input: Original dataset DW, privacy budget ϵ, correlated parameter z, threshold T and query set Q.
Output: Noisy query result M(DW).
(1) Calculate the correlation COR(⋅,⋅) of any two edges in DW according to Eq. (16);
(2) Call Algorithm TBT(DW, T), return DI;
(3) Calculate the correlated sensitivity CS according to Eq. (35);
(4) for (Each f∈Q) do
(5)M(DI)=f(DI)+LaplaceCSϵ;
(6) end for
(7) return Noisy query result M(DI) as M(DW).


## 5.2. Utility Analysis

Clearly, NDR algorithm satisfies theϵ-CEDP model. To conduct utility analysis, we adopt the α,δ-useful definition in [40] to depict the utility of NDR as follows.Definition 14.
A mechanism NDR isα,δ-useful for a query f in all queries Q, if, with probability at least 1-δ, for any query f and dataset D, NDR satisfies maxf∈Q⁡NDRD-fD≤α.Based on Definition14, we obtain the following utility analysis.Theorem 15.
For any queryf∈Q and dataset D, a mechanism NDR satisfies α,δ-useful if NDR can obtain maxf∈Q⁡NDRD-fD≤α with at least probability 1-δ when δ≥exp⁡-ϵα/CS.Proof.
By Definition14, we have(40)Pr⁡maxf∈Q⁡NDRD-fD≤α=Pr⁡maxf∈Q⁡LaplaceCSϵ≤α=∫-ααϵ2CSexp⁡-ϵxCSdx=∫0αϵCSexp⁡-ϵxCSdx=1-exp⁡-ϵαCS.
Ifδ≥exp⁡-ϵα/CS, then the following holds:(41)1-exp⁡-ϵαCS≤1-δ.
According to (40) and (41), we obtain (42)Pr⁡maxf∈Q⁡NDRD-fD≤α≤1-δ.
Therefore, mechanism NDR satisfiesα,δ-useful.


## 6. Experiment

Generally, the goal of privacy preserving is to achieve maximal utilities while maintaining required privacy guarantees; that is, the tradeoff between privacy and utility is desired. In this section, we first present the better privacy guarantees and utilities of Algorithm NDR based on the definition ofα,δ-useful and then further demonstrate its better utilities in terms of mean absolute error (MAE). Here the Baseline algorithm adopts the multiplication in [23] to handle with the correlated tuples in a network dataset. Considering the constraint of applying Pearson correlation coefficient, we do not adopt the method using Pearson correlation coefficient as comparison reference in the following experiments. To verify the advantages of Algorithm NDR concerning privacy and utility, we conduct NDR and Baseline algorithms on three datasets: geom, out explained in Section 4, and randomly generated dataset (rgd), which is a randomly generated weighted network containing 100 vertices and 1645 edges. The weight of each edge is uniformly distributed in interval [1,50]. Such doing can also show the better adaption of the proposed correlation metric and algorithm over real world and synthetic datasets. Without loss of generality, threshold T here is set as 0, and the selection of its value is to be investigated in future work.


### 6.1. Privacy and Utility

We analyzed privacy and utility of NDR and Baseline algorithms in terms ofα,δ-useful when the correlated parameter is set to the size of the whole dataset. In terms of privacy, we evaluate the consumption of privacy budget ϵ under the same accuracy α and the same possibility 1-δ. Clearly, the smaller the consumed privacy budget, the better the performance of algorithm.Figures3(a), 3(c), and 3(e) present the variation of privacy budget, consumed by algorithms NDR and Baseline based on datasets geom, out, and rgd, with the increase of α from 1 to 40 when δ equals 0.1 and 0.5, respectively. From Figures 3(a), 3(c), and 3(e), we can see that privacy budgets decrease in all cases with the increase of α. The reason is that, with the relaxation of α, larger noise can be allowed when δ stays fixed; therefore algorithm can consume smaller privacy budget. Meanwhile, we also see that privacy budgets decrease with the increase of δ from 0.1 to 0.5 when α stays fixed. Because the possibility of satisfying accuracy requirement decreases with the increase of δ, which means that algorithms can have more chances to add larger noise; that is, algorithms can use smaller privacy budget. Such advantage of both algorithms especially in the case of α=1 is more obvious than that of other ones. In fact, when δ stays constant, the higher the accuracy presented by α, the more the privacy budget needed by algorithms.Figure 3
Comparison of privacy and utility on network data in terms ofα,δ-useful.
(a)
Privacy on geom
(b)
Utility on geom
(c)
Privacy on out
(d)
Utility on out
(e)
Privacy on rgd
(f)
Utility on rgdOn the other hand, Figures3(b), 3(d), and 3(f) demonstrate the variation of δ of algorithms NDR and Baseline based on datasets geom, out, and rgd, with the increase of α from 0 to 10000 when ϵ equals 0.1 and 1.0, respectively. We can see that δ decreases in all cases with the increase of α; that is, the possibility increases with the increase of α. Note that this trend varies from dataset to dataset; for example, the possibility and accuracy of algorithm NDR over datasets geom and out are evidently different when ϵ=1. Clearly, when ϵ is determined, the possibility increases with the relaxation of α. In addition, we find that algorithm NDR can have larger possibility, that is, smaller δ, than the Baseline algorithm to achieve the same accuracy α under the same level of privacy budget ϵ. Also, when ϵ increases from 0.1 to 1.0, algorithms also have possibility to achieve the same accuracy α, which is easily understood from (40).


### 6.2. Utility

We adopt MAE, that is,1/|Q|∑f∈Qf^t-ft, to depict the performance of algorithms NDR and Baseline. Obviously, the smaller the MAE value, the better the utility. For each dataset, 10000 queries are randomly generated, and each query result ranges from 0 to the maximal number of tuples.Figures4(a), 4(c), and 4(e) show the variances of MAEs of NDR and Baseline algorithms, over datasets geom, out, and rgd, under various privacy budgets when the correlated parameter z is 10. From Figures 4(a), 4(c), and 4(e), we can see that the MAEs of both algorithms decrease with the increase of privacy budget ϵ from 0.1 to 1. Because larger privacy budget leads to smaller noise added to raw data, the downtrends always hold. More importantly, algorithm NDR can obtain better accuracy, that is, smaller MAE, under various ϵ. Furthermore, the smaller the privacy budget ϵ, the more obvious such advantage. The reason is that algorithm NDR adopts the more reasonable correlation metric compared with the Baseline algorithm.Figure 4
Comparison of utility on network data in terms of mean absolute error.
(a)
Utility on geom (correlated parameterz = 10)
(b)
Utility on geom (privacy budgetϵ = 0.5)
(c)
Utility on out (correlated parameterz=10)
(d)
Utility on out (privacy budgetϵ = 0.5)
(e)
Utility on rgd (correlated parameterz=10)
(f)
Utility on rgd (privacy budgetϵ = 0.5)Figures4(b), 4(d), and 4(f) show the variances of MAEs of NDR and Baseline algorithms, over datasets geom, out, and rgd, under various correlated parameters when privacy budget ϵ is 0.5. In Figures 4(b), 4(d), and 4(f), we find that the MAEs of both algorithms increase with the increase of correlated parameter z from 1 to 40. Undoubtedly, with the increase of the number of correlated tuples in a dataset, larger noise needs to be injected to eliminate the effect of tuple correlation, which necessarily results in the increase of MAE. In addition, we also note that algorithm NDR can obtain better accuracy, that is, smaller MAE, under various correlated parameters compared with the Baseline algorithm. Also, the larger the correlated parameter, the larger such advantage. All these advantages are due to the more reasonable correlation metric, which is proposed in Section 4 and adopted by algorithm NDR.


## 6.1. Privacy and Utility

We analyzed privacy and utility of NDR and Baseline algorithms in terms ofα,δ-useful when the correlated parameter is set to the size of the whole dataset. In terms of privacy, we evaluate the consumption of privacy budget ϵ under the same accuracy α and the same possibility 1-δ. Clearly, the smaller the consumed privacy budget, the better the performance of algorithm.Figures3(a), 3(c), and 3(e) present the variation of privacy budget, consumed by algorithms NDR and Baseline based on datasets geom, out, and rgd, with the increase of α from 1 to 40 when δ equals 0.1 and 0.5, respectively. From Figures 3(a), 3(c), and 3(e), we can see that privacy budgets decrease in all cases with the increase of α. The reason is that, with the relaxation of α, larger noise can be allowed when δ stays fixed; therefore algorithm can consume smaller privacy budget. Meanwhile, we also see that privacy budgets decrease with the increase of δ from 0.1 to 0.5 when α stays fixed. Because the possibility of satisfying accuracy requirement decreases with the increase of δ, which means that algorithms can have more chances to add larger noise; that is, algorithms can use smaller privacy budget. Such advantage of both algorithms especially in the case of α=1 is more obvious than that of other ones. In fact, when δ stays constant, the higher the accuracy presented by α, the more the privacy budget needed by algorithms.Figure 3
Comparison of privacy and utility on network data in terms ofα,δ-useful.
(a)
Privacy on geom
(b)
Utility on geom
(c)
Privacy on out
(d)
Utility on out
(e)
Privacy on rgd
(f)
Utility on rgdOn the other hand, Figures3(b), 3(d), and 3(f) demonstrate the variation of δ of algorithms NDR and Baseline based on datasets geom, out, and rgd, with the increase of α from 0 to 10000 when ϵ equals 0.1 and 1.0, respectively. We can see that δ decreases in all cases with the increase of α; that is, the possibility increases with the increase of α. Note that this trend varies from dataset to dataset; for example, the possibility and accuracy of algorithm NDR over datasets geom and out are evidently different when ϵ=1. Clearly, when ϵ is determined, the possibility increases with the relaxation of α. In addition, we find that algorithm NDR can have larger possibility, that is, smaller δ, than the Baseline algorithm to achieve the same accuracy α under the same level of privacy budget ϵ. Also, when ϵ increases from 0.1 to 1.0, algorithms also have possibility to achieve the same accuracy α, which is easily understood from (40).


## 6.2. Utility

We adopt MAE, that is,1/|Q|∑f∈Qf^t-ft, to depict the performance of algorithms NDR and Baseline. Obviously, the smaller the MAE value, the better the utility. For each dataset, 10000 queries are randomly generated, and each query result ranges from 0 to the maximal number of tuples.Figures4(a), 4(c), and 4(e) show the variances of MAEs of NDR and Baseline algorithms, over datasets geom, out, and rgd, under various privacy budgets when the correlated parameter z is 10. From Figures 4(a), 4(c), and 4(e), we can see that the MAEs of both algorithms decrease with the increase of privacy budget ϵ from 0.1 to 1. Because larger privacy budget leads to smaller noise added to raw data, the downtrends always hold. More importantly, algorithm NDR can obtain better accuracy, that is, smaller MAE, under various ϵ. Furthermore, the smaller the privacy budget ϵ, the more obvious such advantage. The reason is that algorithm NDR adopts the more reasonable correlation metric compared with the Baseline algorithm.Figure 4
Comparison of utility on network data in terms of mean absolute error.
(a)
Utility on geom (correlated parameterz = 10)
(b)
Utility on geom (privacy budgetϵ = 0.5)
(c)
Utility on out (correlated parameterz=10)
(d)
Utility on out (privacy budgetϵ = 0.5)
(e)
Utility on rgd (correlated parameterz=10)
(f)
Utility on rgd (privacy budgetϵ = 0.5)Figures4(b), 4(d), and 4(f) show the variances of MAEs of NDR and Baseline algorithms, over datasets geom, out, and rgd, under various correlated parameters when privacy budget ϵ is 0.5. In Figures 4(b), 4(d), and 4(f), we find that the MAEs of both algorithms increase with the increase of correlated parameter z from 1 to 40. Undoubtedly, with the increase of the number of correlated tuples in a dataset, larger noise needs to be injected to eliminate the effect of tuple correlation, which necessarily results in the increase of MAE. In addition, we also note that algorithm NDR can obtain better accuracy, that is, smaller MAE, under various correlated parameters compared with the Baseline algorithm. Also, the larger the correlated parameter, the larger such advantage. All these advantages are due to the more reasonable correlation metric, which is proposed in Section 4 and adopted by algorithm NDR.


## 7. Conclusion

In this paper, we focus on adopting differential privacy model to avoid the leakage of close relationship between two individuals in a network. To this end, we first extract the PF vector from both aspects of node degree and edge weight to depict an edge in a network dataset and then design the correlation metric of two edges via JS-Divergence to avoid the constraint of adopting Pearson correlation coefficient. Next, we proposed theϵ-CEDP model to deal with the correlated dataset by introducing two parameters including our correlation metric and the correlated parameter. Furthermore, we present the NDR algorithm based on the ϵ-CEDP and discuss its privacy and utility in terms of the definition of α,δ-useful. Extensive experiments on real and synthetic network datasets verify the advantages of our proposed privacy preserving model and algorithm concerning privacy and utility. Admittedly, the proposed solution is currently appropriate for weighted network datasets, and other datasets are out of the scope of this paper. In future work, we will discuss the impacts of choosing weight threshold on algorithm performances, explore more appropriate correlation metrics, and investigate privacy preserving algorithms in different applications.



---

*Source: 8408253-2017-11-13.xml*