# Differential Privacy for Evolving Network Based on GHRG

Authors: Jing Yang; Yuye Wang; Jianpei Zhang
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

Releasing evolving networks which contain sensitive information could compromise individual privacy. In this paper, we study the problem of releasing evolving networks under differential privacy. We explore the possibility of designing a differentially private evolving networks releasing algorithm. We found that the majority of traditional methods provide a snapshot of the networks under differential privacy over a brief period of time. As the network structure only changes in local part, the amount of required noise entirely is large and it leads to an inefficient utility. To this end, we propose GHRG-DP, a novel differentially private evolving networks releasing algorithm which reduces the noise scale and achieves high data utility. In the GHRG-DP algorithm, we learn the online connection probabilities between vertices in the evolving networks bygeneralized hierarchical random graph (GHRG) model. To fit the dynamic environment, a dendrogram structure adjusting method in local areas is proposed to reduce the noise scale in the whole period of time. Moreover, to avoid the unhelpful outcome of the connection probabilities, a Bayesian noisy probabilities calculating method is proposed. Through formal privacy analysis, we show that the GHRG-DP algorithm is ε-differentially private. Experiments on real evolving network datasets illustrate that GHRG-DP algorithm can privately release evolving networks with high accuracy.


---

## Body

## 1. Introduction

As more and more individual information in social network is published, releasing network data might pose threats to individual’s privacy. To protect the privacy of individual information, network data should be sanitized before releasing. Differential privacy has been proposed to address such problem. Unlike the anonymization-based private algorithms (e.g., k-anonymity [1] and l-diversity [2]), differentially private algorithms are randomized algorithms. Differentially private networks releasing algorithms protect the essential structural information and ensure that the connection relationship of each participant is insensitive.In the differentially private static network literature, the standard technique is to add noise to the output of an otherwise non-private algorithm. However, small changes of the network structure should cause a lot of impact point to query answers and it leads to a large amount of perturbation noise. Thus, synthetic network generation methods are used to substitute these standard methods. Roughly speaking, such synthetic network generation methods involve two steps: (1) using the real network to learn the parameters for a model of the network; (2) using the learned model to draw synthetic network from its probability distribution. These synthetic network generation methods could “dilute” the impact of small changes of the network structure by capturing the connection probabilities between vertices.However, the interactions between vertices are often dynamic in nature, and how the network changes deserves to be taken into account. Given a sequence of evolving networks, the standard technique of differential privacy is to add noise to each snapshot of the evolving networks. In this way, each snapshot of the evolving networks satisfies differential privacy individually and turns the static differential privacy algorithm into a “dynamic” version. However, this kind of method suffers from poor performance. The root cause is it leads to a large amount of repetitive perturbation noise. We observe, in practice, the network structure between sequent snapshot changes within a local area. The remaining part of the network is almost unchanged and adding repetitive noise to the same connection probabilities is inefficient. Furthermore, the connection probabilities between vertices of the network may obtain unhelpful outcomes when the connection probabilities equal 0 or 1.To this end, we propose a novel differentially private evolving networks releasing algorithm, called GHRG-DP (i.e., differentially private based on generalized hierarchical random graph). In particular, we first usegeneralized hierarchical random graph (GHRG) model to represent the structure of evolving networks and utilize a hierarchical structure (called dendrogram) of the GHRG model to record connection probabilities between any pair of vertices which have appeared over a period of time. Unlike the popular hierarchical random graph (HRG) model, GHRG allows tree nodes of dendrogram to have any number of children and quantify the change of network’s structure. As the network structure between sequent snapshots changes within a local area, it is important to design a method to generate a good dendrogram of each snapshot of evolving networks. We do not directly generate the best-fitting GHRG by MCMC method, but we generate the GHRG by adjusting the GHRG of the prior time. Then, we model each connection probability as a distribution instead of a point value and add noise to the parameters for the model of the network instead of adding noise to the point value of the connection probability. Finally, we compute connection probabilities’ posterior by Bayesian theory.To make the GHRG-DP satisfy differential privacy, we first sample a GHRG by a Markov chain Monte Carlo (MCMC) method by exponential mechanism while satisfying differential privacy. Then, we adjust the GHRG by exponential mechanism while satisfying differential privacy as well. Thirdly, we add Laplace noise to the parameters for the model of the network. Through formal privacy analysis, we prove that GHRG-DP satisfiesε-differential privacy. In summary, we present several contributions:(1)
We introduce generalized hierarchical random graph model as an effective means of encoding the evolving networks and propose a method to adjust the GHRG model which is suitable for evolving networks.(2)
We develop a novel differentially private evolving networks releasing algorithm, GHRG-DP. To ensure that the releasing evolving networks under differential privacy do not incur excessive noise, we propose a method by adding noise to the parameters for the model of the network.(3)
Through privacy analysis and experiments on real evolving network datasets, we prove that GHRG-DP algorithm can privately release evolving networks with high accuracy.The rest of our paper is organized as follows. Section2 provides a literature review. Section 3 introduces necessary background on differential privacy and hierarchical random graph model. Section 4 identifies the weakness of applying differentially private static network releasing algorithm to evolving networks. In Section 5, we describe our GHRG-DP algorithm in detail. Section 6 gives the privacy analysis. Section 7 reports the experimental results. Section 8 concludes the paper.


## 2. Related Work

Many existing works about social network differential privacy focus on social network analysis. These methods output some network statistics under differential privacy such as degree distribution, subgraph number, and clustering coefficient. In particular, Dwork et al. [3] proposed a differentially private method to answer the queries by adding noise to outcome directly. Hay et al. [4] proposed a differentially private method in a postprocessing phase and computed the consistent input most likely to have produced the noisy output. Hay et al. [5] used this method to estimate the degree distribution. Nissim et al. [6] introduced the concept of smooth sensitivity to protect individuals’ privacy by adding a small amount of random noise to the released statistics, such as triangle count of a network. Zhang et al. [7] analyzed the released statistics through a ladder function and reduced the sensitivity effectively. Cheng et al. [8] presented a two-phase differentially private frequent subgraph mining algorithm called DFG. In DFG, frequent subgraphs are privately identified in the first phase, and the noisy support of each identified frequent subgraph is calculated in the second phase. Ding et al. [9] published the triangle counts satisfying the node-differential privacy with the triangle count distribution and the cumulative distribution. Sun et al. [10] formulated a decentralized differential privacy scheme named DDP, which requires that each participant considers not only their own privacy but also that of their neighbors involved in their ELV. Wang et al. [11] studied the problem of differential privacy for weighted network through the probability model.Differentially private social network releasing algorithm also draws attention. Sala et al. [12] introduced a differentially private graph model called Pygmalion. Pygmalion extracts a graph’s detailed structure into dK-graph, introduces noise into the resulting dataset, and generates a synthetic graph. Lu and Miklau [13] proposed algorithms for privately estimating the parameters of exponential random graph models (ERGMs) of a network. Based on the idea of stochastic Kronecker graph model, Mir and Wright [14] used maximum likelihood estimation to privately estimate the parameters. Xiao et al. [15] proposed a differentially private network publishing method, HRG-MCMC, witch computes an estimator of a given graph in the hierarchical random graph (HRG) model in a differentially private manner and samples possible HRG structures in the model space via Markov chain Monte Carlo (MCMC) witch satisfies the exponential mechanism. Qin et al. [16] investigated techniques to ensure local differential privacy of individuals while collecting structural information and generating representative synthetic social graphs. Chen et al. [17] presented a method for publishing differentially private synthetic attributed graphs, which is able to preserve the community structure of the original graph without sacrificing the ability to capture global structural properties.Many existing works also focus on ensuring dynamic network data privacy. Bhagat et al. [18] analyzed the privacy risks of publishing multiple instances of the same network independently and proposed methods to perform group-based anonymization. Tai et al. [19] introduced the concept of k2-degree anonymity, which limits the probability of a vertex being re-identified to 1/k. Krzysztof Juszczyszy measured the transitions during network evolution by link prediction. Medforth and Wang [20] proposed an anonymization method to solve “degree-tail” attack. Macwan and Patel [21] proposed an anonymization approach to preserve the user identity from all the published time-series datasets of a social network. Yue et al. [22] proposed an efficient and adaptive general graph anonymization framework for incremental data publication. They proposed an anonymization process restart issue (APRI) and designed an activated function to determine whether an anonymization process should be restarted at a certain time in order to solve the problem of high time complexity and large information loss in the incremental data publication. Zhiyuli et al. [23] attempted to model the hierarchical and dynamic features of social networks by designing a damping-based sampling algorithm corresponding to a local search-based incremental learning algorithm, which can easily be extended to large-scale scenarios.Most existing differentially private graph models do not fit evolving network. In this work, we develop a differentially private network publishing method for evolving network.


## 3. Background

### 3.1. Hierarchical Random Graph

Suppose the input network dataset is a simple undirected graphG=V,E, where V is the set of vertices and E⊆V×V is the set of edges. Claustet et al. [24] proposed the hierarchical random graph (HRG) model. HRG uses a hierarchical structure and connection probabilities between any pair of vertices to denote a graph G. The hierarchical structure is represented by a dendrogram T. The dendrogram is a binary tree which has n leaf nodes corresponding to the n vertices. Each internal node r represents a connection probability pr=Er/Nr. In particular, Nr=nLr⋅nRr, where nLr and nRr denote the numbers of leaves of left subtrees Lr and right subtrees Rr, respectively. Er is the number of edges between the leaves of Lr and Rr.Given a graphG, we use the likelihood of the HRG to measure how much it matches G. The likelihood can be calculated as follows:(1)LT,pr=∏r∈TprEr1−prNr−Er,where hpr=−prlogpr−1−prlog1−pr is the Gibbs–Shannon entropy function. A higher likelihood corresponds to a better representation of the network’s structure.


### 3.2. Generalized Hierarchical Random Graph

Peel and Clauset [25] introduced the generalized hierarchical random graph (GHRG) model in 2014. It also defines a couple of data structures T,pr in formal. Unlike the popular HRG model, the GHRG allows the nodes in the dendrogram to have two or more child nodes. It models community structure at all scales and provides accurate fits to social networks. In the dynamic evolving systems, the GHRG could improve the interpretability for varying a network’s structure.


### 3.3. Differential Privacy

Given a graphG, differential privacy ensures that the outputs are approximately the same even if any edge is arbitrarily added or deleted in the graph. Thus, the presence or absence of any edge has a negligible effect on the outputs. We define two graphs G1=V1,E1 and G2=V2,E2 to be neighbors if they satisfy V1=V2, E1⊂E2, and E2=E1+1. ε-differential privacy is defined as follows.Definition 1.
(ε-differential privacy [3]). A randomized algorithm A is ε-differential privacy if for any two neighboring graphs G1 and G2, and for any output O∈RangeA,(2)prAG1∈O≤eεprAG2∈O.
Differential privacy is based on the concept ofglobal sensitivity of a function f. It is used to measure the maximum change in the outputs of f when any edge in the graph is changed. The global sensitivity of f is defined as Δf=maxG1,G2fG1−fG21.
Differential privacy can be achieved by Laplace mechanism and exponential mechanism. The Laplace mechanism is mainly used for functions whose outputs are real values. Differential privacy can be achieved by adding properly noise drawn randomly from Laplace distribution to the true answer.Theorem 1.
(Laplace mechanism [3]). For any function f:G⟶Rd with sensitivity Δf, the algorithm(3)AG=fG+Lap1Δf/ε,…,LapdΔf/ε,satisfies ε-differential privacy, where LapiΔf/ε are i.i.d. Laplace variables with scale parameter Δf/ε.
The exponential mechanism is mainly used for functions whose outputs are not real numbers. The main idea is to sample the output dataO from the output space O according to the utility function u. The global sensitivity of u is Δu=maxO,G1,G2uG1,O−uG2,O.Theorem 2.
(exponential mechanism [26]). Given a graph G and a utility function u:G×O⟶R, the arithmetic A whose output is with probability proportional to expε⋅uG,O/2Δu satisfies ε-differential privacy.Theorem 3.
(sequential composition [27]). If each arithmetic Ai provides εi-differential privacy, a sequence of A1D,A2D,…,A3D over the same database D provides ∑i=1nεi-differential privacy.


## 3.1. Hierarchical Random Graph

Suppose the input network dataset is a simple undirected graphG=V,E, where V is the set of vertices and E⊆V×V is the set of edges. Claustet et al. [24] proposed the hierarchical random graph (HRG) model. HRG uses a hierarchical structure and connection probabilities between any pair of vertices to denote a graph G. The hierarchical structure is represented by a dendrogram T. The dendrogram is a binary tree which has n leaf nodes corresponding to the n vertices. Each internal node r represents a connection probability pr=Er/Nr. In particular, Nr=nLr⋅nRr, where nLr and nRr denote the numbers of leaves of left subtrees Lr and right subtrees Rr, respectively. Er is the number of edges between the leaves of Lr and Rr.Given a graphG, we use the likelihood of the HRG to measure how much it matches G. The likelihood can be calculated as follows:(1)LT,pr=∏r∈TprEr1−prNr−Er,where hpr=−prlogpr−1−prlog1−pr is the Gibbs–Shannon entropy function. A higher likelihood corresponds to a better representation of the network’s structure.


## 3.2. Generalized Hierarchical Random Graph

Peel and Clauset [25] introduced the generalized hierarchical random graph (GHRG) model in 2014. It also defines a couple of data structures T,pr in formal. Unlike the popular HRG model, the GHRG allows the nodes in the dendrogram to have two or more child nodes. It models community structure at all scales and provides accurate fits to social networks. In the dynamic evolving systems, the GHRG could improve the interpretability for varying a network’s structure.


## 3.3. Differential Privacy

Given a graphG, differential privacy ensures that the outputs are approximately the same even if any edge is arbitrarily added or deleted in the graph. Thus, the presence or absence of any edge has a negligible effect on the outputs. We define two graphs G1=V1,E1 and G2=V2,E2 to be neighbors if they satisfy V1=V2, E1⊂E2, and E2=E1+1. ε-differential privacy is defined as follows.Definition 1.
(ε-differential privacy [3]). A randomized algorithm A is ε-differential privacy if for any two neighboring graphs G1 and G2, and for any output O∈RangeA,(2)prAG1∈O≤eεprAG2∈O.
Differential privacy is based on the concept ofglobal sensitivity of a function f. It is used to measure the maximum change in the outputs of f when any edge in the graph is changed. The global sensitivity of f is defined as Δf=maxG1,G2fG1−fG21.
Differential privacy can be achieved by Laplace mechanism and exponential mechanism. The Laplace mechanism is mainly used for functions whose outputs are real values. Differential privacy can be achieved by adding properly noise drawn randomly from Laplace distribution to the true answer.Theorem 1.
(Laplace mechanism [3]). For any function f:G⟶Rd with sensitivity Δf, the algorithm(3)AG=fG+Lap1Δf/ε,…,LapdΔf/ε,satisfies ε-differential privacy, where LapiΔf/ε are i.i.d. Laplace variables with scale parameter Δf/ε.
The exponential mechanism is mainly used for functions whose outputs are not real numbers. The main idea is to sample the output dataO from the output space O according to the utility function u. The global sensitivity of u is Δu=maxO,G1,G2uG1,O−uG2,O.Theorem 2.
(exponential mechanism [26]). Given a graph G and a utility function u:G×O⟶R, the arithmetic A whose output is with probability proportional to expε⋅uG,O/2Δu satisfies ε-differential privacy.Theorem 3.
(sequential composition [27]). If each arithmetic Ai provides εi-differential privacy, a sequence of A1D,A2D,…,A3D over the same database D provides ∑i=1nεi-differential privacy.


## 4. A Straightforward Approach

In this section, we present a straightforward approach to public evolving networks under differential privacy. The main idea of this straightforward approach is to add noise to every snapshot of the evolving network and let the graph of every timestamp satisfy differential privacy. In particular, we first identify the hierarchical random graph (HRG) that best fitsGt. Gt presents the snapshot of evolving networks at time t. And then, we generate G˜t from the identified HRG. Recall that an HRG consists of a dendrogram T and associated probabilities set pr. According to the HRG-MCMC method in [15], we can sample a good dendrogram T by means of Markov chain Monte Carlo (MCMC) procedure which satisfies exponential mechanism. For the associated probabilities set, we add noise to them directly to generate p˜r. At last, we generate G˜t from p˜r and dendrogram T. To satisfy differential privacy, the acceptance ratio paccept is(4)paccept=min1,expε1logLT′/2Δuexpε1logLT/2Δu,where Δu is the global sensitivity of the utility function. It is worth noting that the generating G˜t process of timestamp are independent of each other.


### 4.1. Privacy Analysis of Straightforward Approach

Firstly, at every timestamp, MCMC procedure under exponential mechanism satisfiesε1−differential privacy, and the sensitivity is Δu=logNmax+log1+1/Nmax−1Nmax−1=Ologn. When n is even Nmax=n2/4, and Nmax=n2−1/4 when n is odd. Then, generating p˜r satisfies ε2−differential privacy. Hence, based on the sequential composition, the method in each timestamp satisfies ε1+ε2−differential privacy. When the time span is t, the straightforward approach satisfies tε1+ε2−differential privacy.


### 4.2. The Disadvantage of Straightforward Approach

However, the straightforward approach produces poor results. Firstly, as we observe, the structure of evolving network changes a little most of the time. The structure and the dendrogram of a snapshot are similar to a contiguous snapshot. The straightforward approach samples dendrogramT via MCMC procedure in each timestamp, respectively. It results in a lot of repetitive computation and drastically reduces the utility of the results. Then, the associated probability pr may lead to calculation impairments when we calculate the likelihood function. Consider the case where zero connections Er=0, or all connections Er=Nr; we have pr=0 or 1; thus the likelihood drops to 0 and results in an unhelpful outcome.


## 4.1. Privacy Analysis of Straightforward Approach

Firstly, at every timestamp, MCMC procedure under exponential mechanism satisfiesε1−differential privacy, and the sensitivity is Δu=logNmax+log1+1/Nmax−1Nmax−1=Ologn. When n is even Nmax=n2/4, and Nmax=n2−1/4 when n is odd. Then, generating p˜r satisfies ε2−differential privacy. Hence, based on the sequential composition, the method in each timestamp satisfies ε1+ε2−differential privacy. When the time span is t, the straightforward approach satisfies tε1+ε2−differential privacy.


## 4.2. The Disadvantage of Straightforward Approach

However, the straightforward approach produces poor results. Firstly, as we observe, the structure of evolving network changes a little most of the time. The structure and the dendrogram of a snapshot are similar to a contiguous snapshot. The straightforward approach samples dendrogramT via MCMC procedure in each timestamp, respectively. It results in a lot of repetitive computation and drastically reduces the utility of the results. Then, the associated probability pr may lead to calculation impairments when we calculate the likelihood function. Consider the case where zero connections Er=0, or all connections Er=Nr; we have pr=0 or 1; thus the likelihood drops to 0 and results in an unhelpful outcome.


## 5. GHRG-DP Algorithm in Description

We propose a differentially private evolving networks releasing method, called GHRG-DP. This method is based on generalized hierarchical random graph and can solve the deficiency discussed in Section4. Our solution is composed of two schemes: (1) we propose a dendrogram construction method for evolving network, called dendrogram construction based on adjustment (DCBA) (see Section 5.1). DCBA samples a dendrogram Tsamplet by MCMC process at t time. To achieve differential privacy, we employ the exponential mechanism during the MCMC process. Then, we propose a dendrogram structure adjustment method. We structure a dendrogram Tsamplet+1 of t + 1 time by adjusting the structure of Tsamplet locally. (2) Given the graph Gt and the dendrogram Tsamplet, we propose a noisy probability calculation method based on Bayesian theory (see Section 5.2). In this method, pr will not be a single numerical value, but a distribution. Thus, we could quantify the uncertainty of pr and avoid pr equal to 0 or 1. Then, we calculate the posteriori distribution of pr by Bayesian theory. To achieve differential privacy, we add noise to the parameters or hyperparameters to achieve the noisy probability p˜r. At last, we place edges to G˜t with probability p˜r and get a privatized synthetic graph.


### 5.1. Dendrogram Construction Method: DCBA

Given evolving graphsGn1, we measure how plausible this dendrogram is to represent the graph Gt by the logarithm of the likelihood. This log-likelihood can be computed by Bayes theorem. In fact, we find that the structures of adjacent dendrogram are similar. For example, in dataset AS-733 [28], the log-likelihood of dendrograms in adjacent time changes less than 0.05. Thus, we could get Tsamplet+1 through adjusting Tsamplet locally and reduce the amount of noise we need to add.To this end, we propose a locally dendrogram structure adjustment algorithm, called DCBA (dendrogram construction based on adjustment). The main idea of DCBA is structuring the dendrogram by GHRG model to satisfy the dynamic. When the structure ofGt+1 changes a little compared to Gt, we could get Tsamplet+1 through adjusting Tsamplet locally. Otherwise, we should sample a new Tsamplet+1 through the MCMC algorithm which satisfies the differential privacy. In DCBA, we adjust the structure of dendrogram locally in order to simplify process of structuring the dendrogram. In particular, when a new vertex s is added to Gt+1, based on the GHRG model, we could first, respectively, insert s into Tsamplet as the brother node of each leaf node and get a candidate set of dendrogram. For example, Figure 1 gives an example of the candidate set of dendrogram. Then, we compute the log-likelihood of each candidate. Finally, we choose the dendrogram which has the maximum log-likelihood value to be Tsamplet+1.Figure 1
An example of the candidate set of dendrogram produced by GHRG.The DCBA algorithm is shown in Algorithm1. Given the evolving graphs Gn1, we first judge the change situation of the graph structure at time t + 1 through change-point detection method (line 1). We use the method from [25] to detect the change point and choose threshold. Next, when the change of the graph structure is greater than the threshold, we should sample the dendrogram renewedly through MCMC which simulates the exponential mechanism (lines 2–10). Let the utility function be uT=logLT, where Δu is the sensitivity of the utility function. On the contrary, when the change of the graph structure is less than the threshold, we should adjust the structure of dendrogram locally. We get a candidate set of dendrogram and compute the log-likelihood of each candidate (lines 12–15). Finally, we choose the dendrogram through the exponential mechanism (line 17). Let the utility function be u′Tcandidate=logLTcandidate and we sample Tcandidate with probability proportional to expε3⋅logLTcandidate/2Δu′/∑Tcandidate′∈Texpε3⋅logLTcandidate′/2Δu′. T is the entire candidate set of the new dendrogram. It is easy to know that the global sensitivity Δu′<1 and we set it as 1.Algorithm 1:Dendrogram construction based on adjustment (DCBA).
Input：sampled dendrogram Tsamplet at time t, evolving graphs Gn1, privacy parameter ε1, ε3.Output：sampled dendrogram Tsamplet+1 at time t + 1.(1)
if the result of change-point detection of Gt+1 is true then(2)
Initialize the Markov chain by choosing a random starting dendrogramT0;(3)
fori∈ Markov chain step do(4)
Randomly pick an internal noder in Ti−1;(5)
Pick a neighboring dendrogramT′ of Ti−1 by randomly drawing a configuration of r’s subtrees;(6)
Accept the transition and setTi=T′ with probability min1,expε1logLT′/2Δu1/expε1logLTi−1/2Δu1;(7)
end for(8)
if equilibrium is reached then(9)
Return the sampled dendrogram Tsamplet+1=Ti;(10)
end if(11)
else(12)
for each new node s∈v,v∈Gt+1andv∉Gtdo(13)
for each internal node u whose child nodes are leaves in Tsampletdo(14)
regards as u’child node and construct a candidate set of the new dendrogram;(15)
compute the log-likelihood of each candidatelogLTcandidate ;(16)
end for(17)
sample the new dendrogram with probability proportional toexpε3⋅logLTcandidate/2/∑Tcandidate′∈Texpε3⋅logLTcandidate′/2 from the candidate set;(18)
end for(19)
Return the sampled dendrogram Tsamplet+1;(20)
end if


### 5.2. Noisy Probability Calculation Method: PCBD

The noisy connection probability computing algorithm PCBD is shown in Algorithm2. To avoid connection probability pr to be 0 or 1, we model pr as a distribution and prevent its expected value from becoming 0 or 1. When the Beta distribution has hyperparameters as α = β = 1, it corresponds to a uniform distribution. So, we treat the uniform distribution with the parameter pr as the Beta distribution with hyperparameters α = β = 1. In addition, the Beta distribution is conjugate with the Binomial distribution. When the conjugate prior distribution is the Beta distribution, the posteriori distribution is still the Beta distribution. And when the conjugate prior distribution is the uniform distribution with the parameter pr, the posteriori distribution is the Beta distribution as well. We could get the likelihood through Bayesian theory:(5)pG|T,pr=pG|T,α,β=∏rΓα+βΓαΓβΓEr+αΓNr−Er+βΓNr+α+β.Algorithm 2:Probability calculation based on distribution (PCBD).
Input: evolving graphs Gt+w−1t, sampled dendrogram Tsamplet, privacy parameter ε2, the length of the sliding window w, Tsamplet ’s internal node r∗Output: noisy probabilities p˜rMAPt, r∈r∗,all internal nodes belowr∗(1)
Gt′=Gt∪Gt+1∪⋯∪Gt+w−1;(2)
compute theNr of Gr′ and Er of Gt;(3)
forGi∈Gt,Gt+1,…,Gt+w−1 do(4)
Δαi=ErGi,Δβi=Nr−ErGi;(5)
Δα˜i=ErGi+lap2N/ε2, Δβ˜i=Nr−ErGi+lap2N/ε2;(6)
for end(7)
α˜r′=α+∑i=t,t+1,…,t+w−1Δα˜i,β˜r′=β+∑i=t,t+1,…,t+w−1Δβ˜i;(8)
p˜rMAP=Er+α˜r′/Nr+α˜r′+β˜r′；(9)
for eachr∗’child do(10)
rc←r∗′child;(11)
PCBDGt+w−1t,Tsamplet,ε2,w,rc;(12)
end forGiven the evolving graphs in the sliding windowGt,…,Gt+w−1, where w is the length of the sliding window, we could compute the posteriori distribution prMAP by updating the hyperparameters. prMAP represents the maximum value of pr using Maximum A Posteriori (MAP). We update the hyperparameters as follows:(6)αr′=α+∑Gt,…,Gt+w−1ErGt,βr′=β+∑Gt,…,Gt+w−1Nr−ErGt.Thus, we could obtainprMAP from Er+αr′/Nr+αr′+βr′. To satisfy the differential privacy, we add noise to the hyperparameters αr′ and βr′ with application of the Laplace mechanism. The global sensitivity of PCBD is 2N, where N is the size of the node set which contains the nodes of all the graphs in the sliding window. The reason is that when we insert or delete any edge, the maximum effect it leads to is N. The sanitized hyperparameters are α˜r′=αr′+lap2N/ε2 and β˜r′=βr′+lap2N/ε2, and(7)p˜rMAP=Er+α˜r′Nr+α˜r′+β˜r′.The PCBD algorithm is shown in Algorithm2. In particular, we first get the union set Gt′ which contains all the graphs in the sliding window and compute Nr from Gt′. We should also compute Er from Gt (lines 1-2). Then, we compute the increment of the hyperparameters Δαi and Δβi using Nr and Er of each graph in the sliding window (lines 3-4). To satisfy the differential privacy, we add noise to Δαi and Δβi, and we get Δα˜i and Δβ˜i (line 5). Next, we update the hyperparameters α˜r′ and β′˜ and compute p˜rMAP(lines 7-8). Finally, we use recursion method to compute the noisy probabilities of internal nodes of all the dendrograms.


### 5.3. Generation of Synthetic Graph

After getting the sampled dendrogramTsamplet and the noisy probabilities p˜rMAPt, for each pair of nodes i,j∈Vt, we could find the common ancestor r of i, j which is closest to them. Then, we place an edge Eij with independent probability p˜rMAP and get the synthetic graph G˜t. Algorithm 3 shows the specific process.Algorithm 3:Generate synthetic graph.G˜t.
Input: input graph Gt+w−1t, sampled dendrogram Tsamplet, privacy parameter ε2Output: synthetic graph G˜t(1)
rroot← root node of Tsamplet；(2)
PCBDGt+w−1t,Tsamplet,ε2,w,rroot;(3)
for each pair of vertices i,j∈Vtdo(4)
find the lowest common ancestorr of i and j in Tsamplet;(5)
place an edge inG˜t between i and j with independent probability p˜rMAP；(6)
for end(7)
returnG˜t；


## 5.1. Dendrogram Construction Method: DCBA

Given evolving graphsGn1, we measure how plausible this dendrogram is to represent the graph Gt by the logarithm of the likelihood. This log-likelihood can be computed by Bayes theorem. In fact, we find that the structures of adjacent dendrogram are similar. For example, in dataset AS-733 [28], the log-likelihood of dendrograms in adjacent time changes less than 0.05. Thus, we could get Tsamplet+1 through adjusting Tsamplet locally and reduce the amount of noise we need to add.To this end, we propose a locally dendrogram structure adjustment algorithm, called DCBA (dendrogram construction based on adjustment). The main idea of DCBA is structuring the dendrogram by GHRG model to satisfy the dynamic. When the structure ofGt+1 changes a little compared to Gt, we could get Tsamplet+1 through adjusting Tsamplet locally. Otherwise, we should sample a new Tsamplet+1 through the MCMC algorithm which satisfies the differential privacy. In DCBA, we adjust the structure of dendrogram locally in order to simplify process of structuring the dendrogram. In particular, when a new vertex s is added to Gt+1, based on the GHRG model, we could first, respectively, insert s into Tsamplet as the brother node of each leaf node and get a candidate set of dendrogram. For example, Figure 1 gives an example of the candidate set of dendrogram. Then, we compute the log-likelihood of each candidate. Finally, we choose the dendrogram which has the maximum log-likelihood value to be Tsamplet+1.Figure 1
An example of the candidate set of dendrogram produced by GHRG.The DCBA algorithm is shown in Algorithm1. Given the evolving graphs Gn1, we first judge the change situation of the graph structure at time t + 1 through change-point detection method (line 1). We use the method from [25] to detect the change point and choose threshold. Next, when the change of the graph structure is greater than the threshold, we should sample the dendrogram renewedly through MCMC which simulates the exponential mechanism (lines 2–10). Let the utility function be uT=logLT, where Δu is the sensitivity of the utility function. On the contrary, when the change of the graph structure is less than the threshold, we should adjust the structure of dendrogram locally. We get a candidate set of dendrogram and compute the log-likelihood of each candidate (lines 12–15). Finally, we choose the dendrogram through the exponential mechanism (line 17). Let the utility function be u′Tcandidate=logLTcandidate and we sample Tcandidate with probability proportional to expε3⋅logLTcandidate/2Δu′/∑Tcandidate′∈Texpε3⋅logLTcandidate′/2Δu′. T is the entire candidate set of the new dendrogram. It is easy to know that the global sensitivity Δu′<1 and we set it as 1.Algorithm 1:Dendrogram construction based on adjustment (DCBA).
Input：sampled dendrogram Tsamplet at time t, evolving graphs Gn1, privacy parameter ε1, ε3.Output：sampled dendrogram Tsamplet+1 at time t + 1.(1)
if the result of change-point detection of Gt+1 is true then(2)
Initialize the Markov chain by choosing a random starting dendrogramT0;(3)
fori∈ Markov chain step do(4)
Randomly pick an internal noder in Ti−1;(5)
Pick a neighboring dendrogramT′ of Ti−1 by randomly drawing a configuration of r’s subtrees;(6)
Accept the transition and setTi=T′ with probability min1,expε1logLT′/2Δu1/expε1logLTi−1/2Δu1;(7)
end for(8)
if equilibrium is reached then(9)
Return the sampled dendrogram Tsamplet+1=Ti;(10)
end if(11)
else(12)
for each new node s∈v,v∈Gt+1andv∉Gtdo(13)
for each internal node u whose child nodes are leaves in Tsampletdo(14)
regards as u’child node and construct a candidate set of the new dendrogram;(15)
compute the log-likelihood of each candidatelogLTcandidate ;(16)
end for(17)
sample the new dendrogram with probability proportional toexpε3⋅logLTcandidate/2/∑Tcandidate′∈Texpε3⋅logLTcandidate′/2 from the candidate set;(18)
end for(19)
Return the sampled dendrogram Tsamplet+1;(20)
end if


## 5.2. Noisy Probability Calculation Method: PCBD

The noisy connection probability computing algorithm PCBD is shown in Algorithm2. To avoid connection probability pr to be 0 or 1, we model pr as a distribution and prevent its expected value from becoming 0 or 1. When the Beta distribution has hyperparameters as α = β = 1, it corresponds to a uniform distribution. So, we treat the uniform distribution with the parameter pr as the Beta distribution with hyperparameters α = β = 1. In addition, the Beta distribution is conjugate with the Binomial distribution. When the conjugate prior distribution is the Beta distribution, the posteriori distribution is still the Beta distribution. And when the conjugate prior distribution is the uniform distribution with the parameter pr, the posteriori distribution is the Beta distribution as well. We could get the likelihood through Bayesian theory:(5)pG|T,pr=pG|T,α,β=∏rΓα+βΓαΓβΓEr+αΓNr−Er+βΓNr+α+β.Algorithm 2:Probability calculation based on distribution (PCBD).
Input: evolving graphs Gt+w−1t, sampled dendrogram Tsamplet, privacy parameter ε2, the length of the sliding window w, Tsamplet ’s internal node r∗Output: noisy probabilities p˜rMAPt, r∈r∗,all internal nodes belowr∗(1)
Gt′=Gt∪Gt+1∪⋯∪Gt+w−1;(2)
compute theNr of Gr′ and Er of Gt;(3)
forGi∈Gt,Gt+1,…,Gt+w−1 do(4)
Δαi=ErGi,Δβi=Nr−ErGi;(5)
Δα˜i=ErGi+lap2N/ε2, Δβ˜i=Nr−ErGi+lap2N/ε2;(6)
for end(7)
α˜r′=α+∑i=t,t+1,…,t+w−1Δα˜i,β˜r′=β+∑i=t,t+1,…,t+w−1Δβ˜i;(8)
p˜rMAP=Er+α˜r′/Nr+α˜r′+β˜r′；(9)
for eachr∗’child do(10)
rc←r∗′child;(11)
PCBDGt+w−1t,Tsamplet,ε2,w,rc;(12)
end forGiven the evolving graphs in the sliding windowGt,…,Gt+w−1, where w is the length of the sliding window, we could compute the posteriori distribution prMAP by updating the hyperparameters. prMAP represents the maximum value of pr using Maximum A Posteriori (MAP). We update the hyperparameters as follows:(6)αr′=α+∑Gt,…,Gt+w−1ErGt,βr′=β+∑Gt,…,Gt+w−1Nr−ErGt.Thus, we could obtainprMAP from Er+αr′/Nr+αr′+βr′. To satisfy the differential privacy, we add noise to the hyperparameters αr′ and βr′ with application of the Laplace mechanism. The global sensitivity of PCBD is 2N, where N is the size of the node set which contains the nodes of all the graphs in the sliding window. The reason is that when we insert or delete any edge, the maximum effect it leads to is N. The sanitized hyperparameters are α˜r′=αr′+lap2N/ε2 and β˜r′=βr′+lap2N/ε2, and(7)p˜rMAP=Er+α˜r′Nr+α˜r′+β˜r′.The PCBD algorithm is shown in Algorithm2. In particular, we first get the union set Gt′ which contains all the graphs in the sliding window and compute Nr from Gt′. We should also compute Er from Gt (lines 1-2). Then, we compute the increment of the hyperparameters Δαi and Δβi using Nr and Er of each graph in the sliding window (lines 3-4). To satisfy the differential privacy, we add noise to Δαi and Δβi, and we get Δα˜i and Δβ˜i (line 5). Next, we update the hyperparameters α˜r′ and β′˜ and compute p˜rMAP(lines 7-8). Finally, we use recursion method to compute the noisy probabilities of internal nodes of all the dendrograms.


## 5.3. Generation of Synthetic Graph

After getting the sampled dendrogramTsamplet and the noisy probabilities p˜rMAPt, for each pair of nodes i,j∈Vt, we could find the common ancestor r of i, j which is closest to them. Then, we place an edge Eij with independent probability p˜rMAP and get the synthetic graph G˜t. Algorithm 3 shows the specific process.Algorithm 3:Generate synthetic graph.G˜t.
Input: input graph Gt+w−1t, sampled dendrogram Tsamplet, privacy parameter ε2Output: synthetic graph G˜t(1)
rroot← root node of Tsamplet；(2)
PCBDGt+w−1t,Tsamplet,ε2,w,rroot;(3)
for each pair of vertices i,j∈Vtdo(4)
find the lowest common ancestorr of i and j in Tsamplet;(5)
place an edge inG˜t between i and j with independent probability p˜rMAP；(6)
for end(7)
returnG˜t；


## 6. Privacy Analysis of GHRG-DP

### 6.1. Sensitivity Computation of GHRG-DP

We first analyze the global sensitivityΔu of DCBA algorithm. Δu is the maximum change in the log-likelihood when any edge of graph misses. From [15], we know Δu=maxr∈T−Nrhpr−−Nrhpr′, where pr=Er+αr′/Nr+αr′+βr′,pr′=Er−1+αr′/Nr+αr′+βr′.Theorem 4.
Δu=logw+1Nr−w+1+1+wlog1+w−2+wlog2+w and it is Ologn.Proof.
We first fixNr and treat Er as variable. Let fEr=hpr−hpr′, and we have Δu=maxfEr. For all pr, we have h″pr<0. Then, we could know h′pr=log1−pr−logpr monotonically decreases. Since h′0.5=0, we note that h′pr>0 when pr is in (0,0.5), and h′pr<0 when pr is in (0.5,1]. As hpr has symmetric property, we have Δu=max−minNr⋅fEr,maxNr⋅fEr=maxfEr. When pr=1 or 0, that is, Er=Nr or 1, fEr gets the maximum value. Let Er=1, and we have(8)Δu=Nrhpr−hpr′=Nrprlogpr+1−prlog1−pr−pr′logpr′+1−pr′log1−pr′=Nr|Er+αr′Nr+αr′+βr′logEr+αr′Nr+αr′+βr′+1−Er+αr′Nr+αr′+βr′log1−Er+αr′Nr+αr′+βr′−Er−1+αr′Nr+αr′+βr′logEr−1+αr′Nr+αr′+βr′−1−Er−1+αr′Nr+αr′+βr′log1−Er−1+αr′Nr+αr′+βr′|=NrNr+αr′+βr′1+αr′log1+αr′+Nr−1+βr′logNr−1+βr′−αr′logαr′−Nr+βr′logNr+βr′=1w+1w+1Nr−w+1logw+1Nr−w+1−w+1Nr−wlogw+1Nr−w+k,where the constant k=1+wlog1+w−2+wlog2+w. Let fx=xlogx, we have f′x=1+logx, and Δu≤logw+1Nr−w+1+k+1=OlogNr=Ologn.


### 6.2. Privacy Proof of GHRG-DP

Based on the sequential composition property, we prove that GHRG-DP satisfiesε-differential privacy.Theorem 5.
GHRG-DP satisfiesε-differential privacy.Proof.
We suppose that the length of evolving graphs isT, and there are m change points. Based on the sequential composition property, DCBA algorithm satisfies mε1+T−mε3-differential privacy and PCBD algorithm satisfies Tε2-differential privacy. In Algorithm 3, we know that the synthetic graph is generated through sampled dendrogram and noisy probabilities, and it does not consume any privacy budget. Hence, GHRG-DP satisfies ε-differential privacy, and ε=mε1+T−mε3+Tε2.


## 6.1. Sensitivity Computation of GHRG-DP

We first analyze the global sensitivityΔu of DCBA algorithm. Δu is the maximum change in the log-likelihood when any edge of graph misses. From [15], we know Δu=maxr∈T−Nrhpr−−Nrhpr′, where pr=Er+αr′/Nr+αr′+βr′,pr′=Er−1+αr′/Nr+αr′+βr′.Theorem 4.
Δu=logw+1Nr−w+1+1+wlog1+w−2+wlog2+w and it is Ologn.Proof.
We first fixNr and treat Er as variable. Let fEr=hpr−hpr′, and we have Δu=maxfEr. For all pr, we have h″pr<0. Then, we could know h′pr=log1−pr−logpr monotonically decreases. Since h′0.5=0, we note that h′pr>0 when pr is in (0,0.5), and h′pr<0 when pr is in (0.5,1]. As hpr has symmetric property, we have Δu=max−minNr⋅fEr,maxNr⋅fEr=maxfEr. When pr=1 or 0, that is, Er=Nr or 1, fEr gets the maximum value. Let Er=1, and we have(8)Δu=Nrhpr−hpr′=Nrprlogpr+1−prlog1−pr−pr′logpr′+1−pr′log1−pr′=Nr|Er+αr′Nr+αr′+βr′logEr+αr′Nr+αr′+βr′+1−Er+αr′Nr+αr′+βr′log1−Er+αr′Nr+αr′+βr′−Er−1+αr′Nr+αr′+βr′logEr−1+αr′Nr+αr′+βr′−1−Er−1+αr′Nr+αr′+βr′log1−Er−1+αr′Nr+αr′+βr′|=NrNr+αr′+βr′1+αr′log1+αr′+Nr−1+βr′logNr−1+βr′−αr′logαr′−Nr+βr′logNr+βr′=1w+1w+1Nr−w+1logw+1Nr−w+1−w+1Nr−wlogw+1Nr−w+k,where the constant k=1+wlog1+w−2+wlog2+w. Let fx=xlogx, we have f′x=1+logx, and Δu≤logw+1Nr−w+1+k+1=OlogNr=Ologn.


## 6.2. Privacy Proof of GHRG-DP

Based on the sequential composition property, we prove that GHRG-DP satisfiesε-differential privacy.Theorem 5.
GHRG-DP satisfiesε-differential privacy.Proof.
We suppose that the length of evolving graphs isT, and there are m change points. Based on the sequential composition property, DCBA algorithm satisfies mε1+T−mε3-differential privacy and PCBD algorithm satisfies Tε2-differential privacy. In Algorithm 3, we know that the synthetic graph is generated through sampled dendrogram and noisy probabilities, and it does not consume any privacy budget. Hence, GHRG-DP satisfies ε-differential privacy, and ε=mε1+T−mε3+Tε2.


## 7. Experimental Results

### 7.1. Experiment Settings

We make use of two real-world evolving network datasets in our experiments: AS-caida [28] and AS-733. The dataset contains 122 CAIDA AS graphs, from January 2004 to November 2007. Each file contains a full AS graph derived from a set of RouteViews BGP table snapshots. In our experiment, we extracted snapshots weekly from Jan. 2004 to Apr. 2006. AS-733 collects the communication record of an Autonomous System (AS). It is collected from University of Oregon RouteViews Project. In our experiment, we extracted snapshots daily from Nov. 8, 1997, to Dec. 17, 1997. The statistics of portion data are shown in Tables 1 and 2.Tabel 1
Statistics of AS-caida.
Snapshot1591317212529333740#Nodes1630117160178481874019489203442120221339215482167221885#Edges6591070026743447700279718818828585086566877848865488944Tabel 2
Statistics of AS-733.
Snapshot1591317212529333740#Nodes30153022303730553066309531093130315331663172#Edges53475368536154335440553355505774579858695855We compare the accuracy of GHRG-DP with DDPA [29] and the straightforward method through (1) the relative error of degree distribution and shortest path length distribution (2) the running time. The relative error is represented as(9)rel.err=SG−SavgG˜12.As differential privacy needs to produce random noise, we measure the accuracy of the result by the median relative error where we run the Laplace mechanism 10 times.


### 7.2. Evaluation of GHRG-DP

#### 7.2.1. Comparing with Other Approaches

To show the utility of GHRG-DP algorithm, we first compare the relative error of degree distribution and shortest path length distribution with DDPA and the straightforward method which we have mentioned above. From Figures2 and 3, we can see that GHRG-DP outperforms the DDPA and straightforward method. This is because we add noise to the posterior parameters of the model instead of adding noise to the connection probabilities. GHRG-DP avoids perturbing the connection probabilities directly. Furthermore, we observe that, comparing the variance of the relative error during the entire time series, GHRG-DP also outperforms the straightforward method. This means that the output of GHRG-DP is more stable. This is because, during the process of PCBD algorithm, neighbor networks are similar to each other and it leads to the similar posterior parameters. Thus, the networks GHRG-DP generates are more stable.Figure 2
The relative error of degree distribution. (a) AS-caida. (b) AS-733.
(a)(b)Figure 3
The relative error of shortest path length distribution. (a) AS-caida. (b) AS-733.
(a)(b)Then, we compare the running time with DDPA and the straightforward method. From Table3, we can see that GHRG-DP uses less time than DDPA and the straightforward method takes the most time. This is because, in GHRG-DP, we generate the dendrogram by adjustment in most time and it omits the MCMC process. However, the median of GHRG-DP is much less than the average, and the median of DDPA and the straightforward method is roughly equal to the average. This is because, when the result of change-point detection is false, the adjustment process of dendrogram omits the MCMC computing process. The running time is much less than the straightforward method. However, when the result of change-point detection is true, GHRG-DP needs to sample the dendrogram by MCMC. At this time, the running time is similar. As a result, the running time of GHRG-DP increases, and some part of running time becomes protruding.Tabel 3
Running time evaluation.
DatasetAverage time of GHRG-DP (ms)Average time of DDPA (ms)Average time of straightforward method (ms)AS-caida50661445904AS-73388.511061054DatasetMedian of GHRG-DP (ms)Median of DDPA (ms)Median of straightforward method (ms)AS-caida6259335912AS-733101003995


#### 7.2.2. Evaluation of GHRG-DP on Differentε

In Figures4 and 5, we show how the assignment of privacy parameter affects the performance of GHRG-DP. We fix ε=1.0 and assign ε1,ε2=0.1,0.9,0.3,0.7,0.6,0.4,0.9,0.1 for DCBA and PCBD, respectively. We compare the relative error of degree distribution and shortest path length distribution. From Figures 4 and 5, we can see, when ε1 is relatively large, the relative error always stays high. This is because, in PCBD, we perturb the model parameters and it affects the synthetic graph directly. This means that, compared with the process of sampling dendrogram under differential privacy, the process of perturbing the model parameters affects the performance of GHRG-DP much more.Figure 4
The relative error of degree distribution on differentε. (a) AS-caida. (b) AS-733.
(a)(b)Figure 5
The relative error of shortest path length distribution on differentε. (a) AS-caida. (b) AS-733.
(a)(b)


#### 7.2.3. Evaluation of GHRG-DP on Different Lengths of Sliding Window

In Figures6 and 7, we show how the length of the sliding window affects the performance of GHRG-DP. We set the length to be w=4,8,16,32, respectively. We compare the relative error of degree distribution and shortest path length distribution.Figure 6
The relative error of degree distribution on differentw. (a) AS-caida. (b) AS-733.
(a)(b)Figure 7
The relative error of shortest path length distribution on differentw. (a) AS-caida. (b) AS-733.
(a)(b)Form Figures6 and 7, we can see, when the length of the sliding window is relatively long, the relative error always stays high. This is because, when we update the hyperparameters in PCBD, we need to compute the summation of Δα˜ and Δβ˜ of all the nodes in the sliding window. It generates much cumulate noise.


## 7.1. Experiment Settings

We make use of two real-world evolving network datasets in our experiments: AS-caida [28] and AS-733. The dataset contains 122 CAIDA AS graphs, from January 2004 to November 2007. Each file contains a full AS graph derived from a set of RouteViews BGP table snapshots. In our experiment, we extracted snapshots weekly from Jan. 2004 to Apr. 2006. AS-733 collects the communication record of an Autonomous System (AS). It is collected from University of Oregon RouteViews Project. In our experiment, we extracted snapshots daily from Nov. 8, 1997, to Dec. 17, 1997. The statistics of portion data are shown in Tables 1 and 2.Tabel 1
Statistics of AS-caida.
Snapshot1591317212529333740#Nodes1630117160178481874019489203442120221339215482167221885#Edges6591070026743447700279718818828585086566877848865488944Tabel 2
Statistics of AS-733.
Snapshot1591317212529333740#Nodes30153022303730553066309531093130315331663172#Edges53475368536154335440553355505774579858695855We compare the accuracy of GHRG-DP with DDPA [29] and the straightforward method through (1) the relative error of degree distribution and shortest path length distribution (2) the running time. The relative error is represented as(9)rel.err=SG−SavgG˜12.As differential privacy needs to produce random noise, we measure the accuracy of the result by the median relative error where we run the Laplace mechanism 10 times.


## 7.2. Evaluation of GHRG-DP

### 7.2.1. Comparing with Other Approaches

To show the utility of GHRG-DP algorithm, we first compare the relative error of degree distribution and shortest path length distribution with DDPA and the straightforward method which we have mentioned above. From Figures2 and 3, we can see that GHRG-DP outperforms the DDPA and straightforward method. This is because we add noise to the posterior parameters of the model instead of adding noise to the connection probabilities. GHRG-DP avoids perturbing the connection probabilities directly. Furthermore, we observe that, comparing the variance of the relative error during the entire time series, GHRG-DP also outperforms the straightforward method. This means that the output of GHRG-DP is more stable. This is because, during the process of PCBD algorithm, neighbor networks are similar to each other and it leads to the similar posterior parameters. Thus, the networks GHRG-DP generates are more stable.Figure 2
The relative error of degree distribution. (a) AS-caida. (b) AS-733.
(a)(b)Figure 3
The relative error of shortest path length distribution. (a) AS-caida. (b) AS-733.
(a)(b)Then, we compare the running time with DDPA and the straightforward method. From Table3, we can see that GHRG-DP uses less time than DDPA and the straightforward method takes the most time. This is because, in GHRG-DP, we generate the dendrogram by adjustment in most time and it omits the MCMC process. However, the median of GHRG-DP is much less than the average, and the median of DDPA and the straightforward method is roughly equal to the average. This is because, when the result of change-point detection is false, the adjustment process of dendrogram omits the MCMC computing process. The running time is much less than the straightforward method. However, when the result of change-point detection is true, GHRG-DP needs to sample the dendrogram by MCMC. At this time, the running time is similar. As a result, the running time of GHRG-DP increases, and some part of running time becomes protruding.Tabel 3
Running time evaluation.
DatasetAverage time of GHRG-DP (ms)Average time of DDPA (ms)Average time of straightforward method (ms)AS-caida50661445904AS-73388.511061054DatasetMedian of GHRG-DP (ms)Median of DDPA (ms)Median of straightforward method (ms)AS-caida6259335912AS-733101003995


### 7.2.2. Evaluation of GHRG-DP on Differentε

In Figures4 and 5, we show how the assignment of privacy parameter affects the performance of GHRG-DP. We fix ε=1.0 and assign ε1,ε2=0.1,0.9,0.3,0.7,0.6,0.4,0.9,0.1 for DCBA and PCBD, respectively. We compare the relative error of degree distribution and shortest path length distribution. From Figures 4 and 5, we can see, when ε1 is relatively large, the relative error always stays high. This is because, in PCBD, we perturb the model parameters and it affects the synthetic graph directly. This means that, compared with the process of sampling dendrogram under differential privacy, the process of perturbing the model parameters affects the performance of GHRG-DP much more.Figure 4
The relative error of degree distribution on differentε. (a) AS-caida. (b) AS-733.
(a)(b)Figure 5
The relative error of shortest path length distribution on differentε. (a) AS-caida. (b) AS-733.
(a)(b)


### 7.2.3. Evaluation of GHRG-DP on Different Lengths of Sliding Window

In Figures6 and 7, we show how the length of the sliding window affects the performance of GHRG-DP. We set the length to be w=4,8,16,32, respectively. We compare the relative error of degree distribution and shortest path length distribution.Figure 6
The relative error of degree distribution on differentw. (a) AS-caida. (b) AS-733.
(a)(b)Figure 7
The relative error of shortest path length distribution on differentw. (a) AS-caida. (b) AS-733.
(a)(b)Form Figures6 and 7, we can see, when the length of the sliding window is relatively long, the relative error always stays high. This is because, when we update the hyperparameters in PCBD, we need to compute the summation of Δα˜ and Δβ˜ of all the nodes in the sliding window. It generates much cumulate noise.


## 7.2.1. Comparing with Other Approaches

To show the utility of GHRG-DP algorithm, we first compare the relative error of degree distribution and shortest path length distribution with DDPA and the straightforward method which we have mentioned above. From Figures2 and 3, we can see that GHRG-DP outperforms the DDPA and straightforward method. This is because we add noise to the posterior parameters of the model instead of adding noise to the connection probabilities. GHRG-DP avoids perturbing the connection probabilities directly. Furthermore, we observe that, comparing the variance of the relative error during the entire time series, GHRG-DP also outperforms the straightforward method. This means that the output of GHRG-DP is more stable. This is because, during the process of PCBD algorithm, neighbor networks are similar to each other and it leads to the similar posterior parameters. Thus, the networks GHRG-DP generates are more stable.Figure 2
The relative error of degree distribution. (a) AS-caida. (b) AS-733.
(a)(b)Figure 3
The relative error of shortest path length distribution. (a) AS-caida. (b) AS-733.
(a)(b)Then, we compare the running time with DDPA and the straightforward method. From Table3, we can see that GHRG-DP uses less time than DDPA and the straightforward method takes the most time. This is because, in GHRG-DP, we generate the dendrogram by adjustment in most time and it omits the MCMC process. However, the median of GHRG-DP is much less than the average, and the median of DDPA and the straightforward method is roughly equal to the average. This is because, when the result of change-point detection is false, the adjustment process of dendrogram omits the MCMC computing process. The running time is much less than the straightforward method. However, when the result of change-point detection is true, GHRG-DP needs to sample the dendrogram by MCMC. At this time, the running time is similar. As a result, the running time of GHRG-DP increases, and some part of running time becomes protruding.Tabel 3
Running time evaluation.
DatasetAverage time of GHRG-DP (ms)Average time of DDPA (ms)Average time of straightforward method (ms)AS-caida50661445904AS-73388.511061054DatasetMedian of GHRG-DP (ms)Median of DDPA (ms)Median of straightforward method (ms)AS-caida6259335912AS-733101003995


## 7.2.2. Evaluation of GHRG-DP on Differentε

In Figures4 and 5, we show how the assignment of privacy parameter affects the performance of GHRG-DP. We fix ε=1.0 and assign ε1,ε2=0.1,0.9,0.3,0.7,0.6,0.4,0.9,0.1 for DCBA and PCBD, respectively. We compare the relative error of degree distribution and shortest path length distribution. From Figures 4 and 5, we can see, when ε1 is relatively large, the relative error always stays high. This is because, in PCBD, we perturb the model parameters and it affects the synthetic graph directly. This means that, compared with the process of sampling dendrogram under differential privacy, the process of perturbing the model parameters affects the performance of GHRG-DP much more.Figure 4
The relative error of degree distribution on differentε. (a) AS-caida. (b) AS-733.
(a)(b)Figure 5
The relative error of shortest path length distribution on differentε. (a) AS-caida. (b) AS-733.
(a)(b)


## 7.2.3. Evaluation of GHRG-DP on Different Lengths of Sliding Window

In Figures6 and 7, we show how the length of the sliding window affects the performance of GHRG-DP. We set the length to be w=4,8,16,32, respectively. We compare the relative error of degree distribution and shortest path length distribution.Figure 6
The relative error of degree distribution on differentw. (a) AS-caida. (b) AS-733.
(a)(b)Figure 7
The relative error of shortest path length distribution on differentw. (a) AS-caida. (b) AS-733.
(a)(b)Form Figures6 and 7, we can see, when the length of the sliding window is relatively long, the relative error always stays high. This is because, when we update the hyperparameters in PCBD, we need to compute the summation of Δα˜ and Δβ˜ of all the nodes in the sliding window. It generates much cumulate noise.


## 8. Conclusions

In this paper, we investigate the problem of evolving network differential privacy. We first introduce a straightforward approach for publishing differentially private evolving network. This approach sanitizes each timestamp network, respectively. We observe that the amount of noise required in straightforward approach is really high. Thus, we propose our GHRG-DP algorithm. The main idea is adjusting the structure of dendrogram to reduce the amount of noise during the process of MCMC. We change the real value of connection to the distribution of connection probability. It satisfies the differential privacy through adding noise during the iteration process of updating the hyperparameters. It could fit the dynamic environment of evolving network. Formal privacy analysis and the results of extensive experiments show GHRG-DP can achieve a private evolving network with high utility. Our future research directions are the more effective change-point detection method in Algorithm1 under differential privacy.



---

*Source: 6783949-2020-12-03.xml*