key: cord-0304671-mfzziq3j
authors: Laeuchli, Jesse; Ram'irez-Cruz, Yunior; Trujillo-Rasua, Rolando
title: Analysis of centrality measures under differential privacy models
date: 2021-03-05
journal: nan
DOI: 10.1016/j.amc.2021.126546
sha: 26d01befcff8b9ad7d7cbff52f7e94e51a4ef5ec
doc_id: 304671
cord_uid: mfzziq3j

This paper provides the first analysis of the differentially private computation of three centrality measures, namely eigenvector, Laplacian and closeness centralities, on arbitrary weighted graphs, using the smooth sensitivity approach. We do so by finding lower bounds on the amounts of noise that a randomised algorithm needs to add in order to make the output of each measure differentially private. Our results indicate that these computations are either infeasible, in the sense that there are large families of graphs for which smooth sensitivity is unbounded; or impractical, in the sense that even for the cases where smooth sensitivity is bounded, the required amounts of noise result in unacceptably large utility losses.

Online social networks are pervasive nowadays. Social interactions via digital means, such as chat apps, electronic mail, discussion forums and social networking websites, are typically chosen over traditional face-to-face interactions for various reasons. It could be that digital interaction is convenient and efficient, or that it is simply the only available communication channel, as in the current COVID-19 crisis. In either case, the result is a massive amount of digital information for the public and private sectors alike to perform social analysis and improve or optimise their services.

Typical social network analysis tasks are, among others, community detection, which allows to detect groups of users that display a common behaviour or are somehow strongly interrelated; link prediction, commonly used for suggesting new friends; and centrality analysis, which helps to determine the role a user plays in the network. The challenge is that, allowing accurate analyses on a dataset while, at the same time, protecting users' private information are conflicting goals [6] . Even aggregated information, such as election results, has the potential to unwillingly reveal sensitive information, such as people's vote. An extreme, yet illustrative example is an election result where a candidate gets all possible votes. That reveals, not only the preference of the population, but also the choice that each citizen made at an individual level. One may argue that when an attribute is shared by many it becomes less sensitive. However, this is likely not the case for attributes such as chronic diseases, even though they are suffered by a large part of the population.

What information needs protection and how information may be leaked are fundamental questions that privacy notions, models and frameworks have attempted to answer. In general, answers to those questions vary depending on the type of information that is being collected and analysed. Voters may want to keep their votes secret, users in a social network may like to protect their relationships with others, etc. This explains the explosion of privacy models that can be found in literature; each addressing a specific scenario; each unable to claim privacy outside of its application domain.

In 2006, Dwork, McSherry, Nissim and Smith formulated privacy in a different way [5] . They addressed the question of how a data holder can promise to each user that the analysis results will be independent (up to some extent) of their contribution to the dataset. Rather than defining what information needs protection, Dwork et al. aimed at ensuring that the fact that an indi-vidual contributed her data to a survey is unlikely to be determined from the output of the analyses, regardless of what the survey is about. The resulting privacy definition, called differential privacy (DP), is formalised as follows.

Definition 1.1 ((ε, δ)-differential privacy). Let D be a universe of datasets and ∼ a symmetric and anti-reflexive neighbouring relation on D relating two datasets if one can be obtained from the other by adding or removing one entry. A randomised algorithm A : D → O, for some co-domain O, is (ε, δ)-differentially private if for all S ⊆ O and every x, y ∈ D such that x ∼ y:

Pr(A(x) ∈ S) ≤ e ε Pr(A(y) ∈ S) + δ.

As Definition 1.1 indicates, randomisation is an essential component of differential privacy. In fact, no deterministic algorithm satisfies this privacy notion.

This paper addresses the problem of providing information about the importance of users in a social network in a differentially private manner. We consider that the ability of determining the status of users within their social network is useful, but we consider revealing the connectivity information between two users to be a privacy intrusion . For example, in the social network induced by the contact tracing data collected by governments during the COVID-19 pandemic, determining high-centrality individuals helps health authorities to more efficiently allocate scarce resources such as testing capabilities. However, while conducting this study, individuals (especially those who test negative) must be protected from the risk of having their potentially sensitive contact information revealed.

There exist various centrality measures to calculate the importance of a user in a social network. Yet, only degree centrality has been made differentially private while preserving the node ordering induced by the noiseless measure [8] , which is arguably the most relevant utility criterion for centrality measures. Considering that different centrality measures provide different insights on the role of nodes in a graph, it is of considerable interest to understand to what extend other centrality measures are amenable to differential privacy.

Contributions. This article provides the first analysis of the eigenvector, Laplacian and closeness graph centrality measures under the differential privacy model. An observation that has been made in previous work, albeit no proof has been provided, is that the use of the Laplace mechanism [6] in most centrality measures leads to unbounded noise. Our analyses confirm such claim for the centrality measures under study, and we go further by characterising the noise incurred by the smooth sensitivity mechanism [18] , which claims to reduce noise with respect to the Laplace mechanism. We provide lower and upper bounds on the noise needed to make each centrality measure differentially private based on the smooth sensitivity mechanism. We compare these bounds to the level of tolerable noise for each measure, defined as the amount of noise under which the node ordering induced by the centrality measure remains close to the original ordering with high probability. This comparison allows us to draw three different conclusions on the feasibility of using smooth sensitivity on a given centrality measure. If the tolerable noise is below the lower bound, then our results render accurate smooth sensitivity-based differential privacy infeasible. If the tolerable noise is above the upper bound, then the randomised algorithms described in this article can be used as effective and useful differentially private methods. Otherwise, if the tolerable noise is in between the lower and upper bound, we cannot draw any meaningful conclusion, except that further investigation is required. We empirically illustrate the trade-off between privacy and accuracy in real-life and synthetic social graphs for the three centrality measures.

Organisation. The rest of this paper is organised as follows. We first review related work in Section 2. Then, we formally enunciate the scope of our study in Section 3. Theoretical results for eigenvector, Laplace and closeness centralities are given in Sections 4, 5 and 6, respectively, whereas empirical results are presented in Section 7. Finally, we give our conclusions in Section 8.

The Laplace mechanism, which consists in adding noise drawn from a Laplace distribution with mean zero and variance 2 (∆f /ε) 2 , is the most common approach to satisfy differential privacy [6] . In the previous formula, f is the query function of interest, ε the privacy parameter, and ∆f the global sensitivity of f , defined as ∆f = max x,y∈D,x∼y f (x) − f (y) 1 . Because noise is proportional to global sensitivity, and many useful functions have large global sensitivity, Nissim et al. later introduced a sampling method based on smooth sensitivity [18] , which claims to reduce noise with respect to the Laplace mechanism.

For graphs, the general notion of (ε, δ)-differential privacy has been instantiated in several ways, each depending on the definition of the neighbouring dataset relation ∼. The most commonly used notion, (ε, δ)-edge differential privacy, states that two graph datasets are neighbouring if they differ in exactly one edge. In this case, differential privacy ensures that the output of the function does not leak information as to whether two users are connected. Alternatively, two graphs are considered as vertex-neighbouring if they differ by exactly one vertex, and all edges incident to that vertex. In this case, differential privacy ensures that the output of the algorithm does not leak information as to whether a user is in the graph. In this paper, we use a generalisation of (ε, δ)-edge differential privacy for the case of edge-weighted graphs.

Differentially private degree sequences [8, 13] , and the related notion of degree correlations [22] , were the earliest focus of research on the application of differential privacy to graph data. The degree sequence of a graph is a particularly good statistic in terms of amenability to differential privacy, especially under the notion of edge-differential privacy, as it requires to add very small amounts of noise to guarantee privacy. This has allowed studies to deepen on techniques for improving the final (post-processed) results. The general trend in publishing these statistics under DP consists in adding noise to the original sequences and then post-processing the perturbed sequences to enforce or restore certain properties, such as graphicality [13] , vertex order in terms of degrees [8] , etc. These studies are also particularly relevant from the perspective of this paper, as degree is the most straightforward vertex centrality measure. To the best of our knowledge, degree is in fact the only vertex centrality measure for which differentially private methods have been proposed, and the present paper is the first comprehensive analysis in this field.

Computing degree sequences and degree correlations is often seen as an intermediate step in building graph generative models, from which synthetic graphs are later sampled and released to analysts [16, 13, 19, 22, 25, 10, 1] . Under this approach, differential privacy is applied in computing model parameters, and sampling is performed as post-processing, so the synthetic graphs preserve the same privacy guarantees as the models themselves. In addition to degree sequences and degree correlations, a differentially private version of the Kronecker graph model [14] is used in [16] , whereas the dK-graph model, which is based on differentially privately counting the occurrences of specific subgraphs with K vertices (e.g. length-K paths) is introduced in [19] . The hierarchical random graph (HRG) model [2] was shown in [25] to allow for further reductions of the amount of added noise. Furthermore, a differentially private version of the attributed graph model (AGM) [9] was introduced in [10], allowing to generate differentially private graphs featuring attributed nodes. This approach was extended in [1] to account for the community structure of the graph. The aforementioned generative model-based approaches have required to develop mechanisms for computing additional graph statistics under DP, e.g. community partitions [17] and subgraph count queries such as the number of length-K paths [19] and the number of triangles of either the entire graph [12, 23, 26] or that of a subgraph [1] .

Recently, differentially private methods leveraging the randomized response strategy for publishing a graph's adjacency matrix were proposed in [20] . Randomized response treats the adjacency matrix of the graph as a series of answers to the yes/no question "are vertices u and v connected? ", instead of numerical values. Thus, the randomisation is achieved by giving the true answer to this question with a given probability p, and a random answer with probability 1 − p.

Differentially private computation methods for other graph problems, including vertex cover, set cover, min-cut and k-median, are described in [7] . Despite the existence of the aforementioned results, it is important to highlight that the accurate, differentially private computation of very basic graph queries, e.g. graph diameter, has revealed to be infeasible or considerably challenging. This paper contributes several results of this type concerning centrality measures, as we show that there exist graph families for which a meaningful privacy protection in the computation of closeness, eigenvector and Laplacian centralities leads to arbitrarily inaccurate node rankings.

This section introduces notation and definitions necessary to formalise the privacy problem we address. In particular, we define the type of data to be analysed, the information to be queried from data, the information we intend to protect and the privacy-preserving technique used to protect that information.

The type of graphs we consider are weighted, connected and undirected. We use G = (V, E, W ) to denote one of such graphs, where V is a set of vertices, E a symmetric relation on the set of vertices representing edges, and W : V × V → R + a total function mapping weights to edges. Because G is undirected,

We also require consistency between E and W , in the sense that

That is, edges in E must feature non-zero weights, whereas the weight of a non-existing edge is considered to be zero by convention. We use G to denote the universe of graphs of the type described above.

Vertex centrality measures score the structural importance of users within a social graph. In this paper, we treat a centrality measure as a function on (a subset of) G yielding a vector (y 1 , . . . , y n ) ∈ R n , where n is the order of the input graph (which corresponds to the number of users in the network). Formally, in order to account for graphs of different order, we define a centrality measure as a finite family of functions

and its co-domain is R i . For the sake of simplicity, we assume that vertices in a graph satisfy an arbitrary, but fixed, total order. That is, given a graph G = (V, E, W ) it holds that V is isomorphic to {1, . . . , |V |} under the total order <. Intuitively, given a graph G of size n and a centrality measure C n , the vector C n (G) = (y 1 , . . . , y n ) assigns a score to each vertex in the network which quantifies its centrality. Considering v 1 < v 2 < . . . < v n to be the totally ordered set of vertices of G, we say that v i is more important (or more central) than v j (for any pair i, j ∈ {1, . . . , n}) if and only if y i > y j .

Although we allow the vector of centrality scores to be obtained from the social graph, we claim that information on the users relations, i.e. the weights of the connections among users in the graph, should remain private. This protects users from adversaries willing to learn how they interact with each other. For example, consider a social graph where the weight of each edge depends on the number of e-mails exchanged between the two connected users. Assuming the social graph belongs to a company X, it may not come as a surprise that top executives play central roles in that graph. Yet, revealing the number of e-mails exchanged by, for instance, the company manager with the rest of employees, may compromise the company's private operations or even leak the nature of the manager's personal relations with other employees. We consider in this article a generalisation of the popular edge-neighbouring relation [8, 13, 23, 12, 26, 17, 1] , which allows to reason about the protection of the weight of a connection rather than its mere existence. We call this neighbouring relation the θ-edge neighbouring and define it as follows. 

The neighbouring relation ∼ e θ can be defined algorithmically as follows: two graphs G 1 and G 2 are neighbouring if G 1 can be obtained from G 2 by increasing or decreasing the weight of one and only one edge in G 2 by up to a maximum value θ. Therefore, a differentially private output with respect to ∼ e θ will guarantee that the adversary cannot differentiate the real graph from another one where the weight of a given edge differs by less than θ. That is, the adversary can determine with sufficient certainty that the weight value lies in some interval, but cannot improve the granularity of this interval beyond a radius θ without sacrificing certainty. In particular, if θ equals the maximum weight of an edge, then differential privacy based on the notion of θ-edge neighbouring datasets can be used to effectively prevent the adversary from learning the weight of any edge. For ease of exposition and whenever it does not lead to confusion, we will use in the remainder of this article ∼ as a shorthand notation for ∼ e θ .

In order to make a centrality measure C n differentially private, one needs to add noise to the outputs of C n . The Laplace mechanism [6] adds noise proportional to the difference between the outputs of C n on every pair of sufficiently close inputs. Such a difference is known as global sensitivity.

Definition 3.2 (Global sensitivity). Let f : G → R n be a deterministic function whose co-domain is the real coordinate space of n dimensions. Global sensitivity with respect to ∼ and f is defined as follows.

The second randomised mechanism that we employ in this article is based on a less stringent notion of sensitivity called smooth sensitivity [18, 12] , which, rather than considering any pair of neighbouring graphs, depends on the raw graph and considers its neighbouring graphs. Definition 3.3 (β-smooth sensitivity). Let f : G → R n be a deterministic function and ∼ a neighbouring relation between graphs. Let d : G × G → R be a distance measure defined by d(x, y) = k if k is the smallest positive integer such that there exists z 0 , . . . , z k ∈ G satisfying that z 0 = x, z k = y and z 0 ∼ · · · ∼ z k . Given a real value β, the β-smooth sensitivity of f around

where LS ∼ f (y) = max G ′ ∈G,G∼G ′ C n (G) − C n (G ′ ) 1 is known as the local sensitivity of y with respect to f and ∼.

Local and smooth sensitivity have been used as auxiliary tools in differentially private computations [12, 26, 1] . However, there does not exist yet a procedure to calculate or estimate these parameters with respect to standard centrality measures, such as eigenvector, Laplacian and closeness centralities. In what follows, we address that limitation by providing bounds on the global, local and smooth sensitivities of the three centrality measures under study.

Eigenvector centrality uses linear algebraic properties of the adjacency matrix of a graph to determine the influence of each node. The centrality score of a node u, denoted e-score G (u), is calculated recursively as the weighted sum of the scores of its neighbours divided by a constant λ.

Let C e n denote the eigenvector centrality function with domain G n and co-domain R n defined as

for every graph G with totally ordered set of vertices v 1 < . . . < v n . Let A be the weight (positive) matrix of G. Then we may write, λ × C e n (G) = A × C e n (G) This means that C e n (G) is an eigenvector of A with corresponding eigenvalue λ. Note that for this centrality measure we are not interested in every eigenvector, but rather the one with the largest associated eigenvalue. To summarise, the eigenvector centrality function C e n (G) of a graph G is the eigenvector associated with the largest eigenvalue of the weight (positive) matrix of G.

We start by analysing the local sensitivity of C e n (G). 

Note that such a pair of vertices ought to exist as G = G ′ . It follows that the adjacency matrix A ′ of G ′ is related to the adjacency matrix of G by A ′ = A + εv i ·v j T . This means that,

First, notice that the eigenvectors v(A) and v(

where Θ(v(A), v(A ′ )) denotes the angle between v(A) and v(A ′ ). Now, from Davis-Kahan [3] we have that

Using the fact that |ε| ≤ |θ| we conclude the proof.

In the worst case, these bounds are tight. However, if one restricts the graph models under consideration, it is possible to obtain tighter bounds [11] .

Here we consider only the general case, and leave more restricted models for future work. Having bounded the local sensitivity, we would now like to use this to bound β-smooth sensitivity. Unfortunately, for weighted graphs, β-smooth sensitivity can be arbitrarily large, as shown next.

Theorem 4.2. There exists a weighted connected graph G such that its β-smooth sensitivity S * C e n ,β (G) is unbounded. Proof. We proceed by construction of an example. We wish to bound

Therefore it suffices to show that there is some G, that has a nearby neighbour G ′ with an arbitrarily bad spectral gap. An example of such graph G is demonstrated in what follows. Consider a simple graph with two vertices a, b. Each vertex is linked to the other by an edge with weight θ + ǫ, where ǫ is some constant, which we set arbitrarily close to zero. In this case the eigenvalues of G's adjacency matrix A are λ 1 = θ + ǫ, and λ 2 = −(θ + ǫ). After making a θ reduction to the edge weight we now have λ 1 = ǫ, and λ 2 = −(ǫ), giving a spectral gap of |2ǫ|. We thus have

Since ǫ can be made arbitrarily close to zero, the smooth sensitivity of G becomes arbitrarily large. Theorem 4.2 agrees with results previously determined by [21] , showing that if a graph has a bad spectral gap, then no useful centrality rankings can be computed, which agrees with our bound above. Another way of looking at this result is that as long as there is a graph in the neighbourhood of G with a bad spectral gap we have to add enough noise to the graph to completely remove any utility from the centrality measure. This is analysed in detail in what follows.

We explain the impact on utility from adding noise proportional to the bound on local sensitivity given above. Since local sensitivity serves as a lower bound on smooth sensitivity, the fact that this amount of noise, which still guarantees no privacy, is already sufficient for destroying utility, means that (ε, δ)-differentially private versions of this method are impractical. Consider the centrality ranking shown in Figure 1 . Here we have a situation that is nearly optimal for centrality ranking algorithms. We have a small percentage of nodes that are very important, and a vast majority of nodes that are not important at all. The important nodes are separated from the unimportant nodes by a gap of ψ. Given the upper bounds for local sensitivity we have previously computed, we show that we will missclassify all the nodes with high probability, unless the gap ψ is unrealistically large. Since in practice the distribution of node centrality will be much less optimally distributed, this means that after adding noise calibrated to smooth sensitivity we will, in general, preserve no to little utility. In order to enforce privacy, we need to add a noise vector consisting of n random variables from the Laplace distribution L(0, b), where b is the bound we previously computed for the local sensitivity. This means that our distribution has a variance of 2b 2 , and a mean 0. Proof. In order to misclassify an unimportant node as an important node, we must add noise proportional to the gap ψ. We are computing the noise as a vector of n i.i.d random variables drawn from a Laplace distribution L(0, b),

is the spectral gap of A. Since we are working with the Laplace distribution we can use the cumulative distribution function

2 ), x ≥ 0 to compute the probability that an element of our noise vector is greater than ψ. Then, n times this probability will be the number of misclassified vertices. We wish to compute the minimum size so that the number of misclassified vertices is less than some constant amount c. We thus have

A gap of O( (n)) is grossly unrealistic even for graphs that have an extremely favourable centrality ranking. Since the bounds on local sensitivity for eigenvector centrality are tight for some graphs, in the worst case we cannot offer any computational utility after adding noise. We leave open the question of what the average case is for local sensitivity. However, since local sensitivity serves as a lower bound on smooth sensitivity, it seems likely that in practice the average case is not much better than the worst case. In Section 7 we present empirical results which support this claim.

Let G be an undirected and weighted graph with vertices {v 1 , . . . , v n } and weight matrix W . The Laplacian matrix of G is defined by L = X − W , where X is the diagonal matrix satisfying that X ii = n j=1 W ij for every i ∈ {1, . . . , n}.

The Laplace energy of G, denoted Λ(G), is the sum of the squares of the eigenvalues of the Laplacian matrix of G, i.e. Λ(G) = λ 2 1 + · · · + λ 2 n where λ 1 , · · · , λ n are the eigenvalues of G. Considering G v i to be the graph resulting from removing v i from G, the Laplacian centrality vector of a graph G is the vector C n L (G) = (c 1 , . . . , c n ) where,

We wish to bound LS ∼ C n

, and then use this to bound S * C n L ,β . We will make use of two well known theorems. The first is Weyl interlacing inequality theorem [24] . This theorem states that given two Hermitian matrices A, with eigenvalues λ i , and a Hermitian perturbation matrix P , one can define a new matrix M = A+P , and bound its eigenvalues. In particular, the eigenvalues µ i of M are bounded by |µ i − λ i | ≤ P . Here the norm may be any consistent matrix norm, so we consider the P ∞ norm. We note that if we make k changes of size θ to G, then P ∞ = kθ.

We will also make use of a theorem from [15] , which states that for an unweighted graph the eigenvalues of a graph created by deleting a vertex v i are bounded as

where λ v i are the eigenvalues of the new graph Laplacian, and λ are the eigenvalues of the original graph. We begin by extending this theorem to weighted graphs. In doing so we follow the same argument as the original theorem. 

Finally let the eigenvalues of P be ρ n ... ≥ ρ i ... ≥ ρ 1 . Then we have λ i − δ ≤ λ v i . Proof. Since our graph is undirected, we have that L is a symmetric matrix, therefore by the Cauchy interlacing theorem, we have that λ 1 ≤ ρ i .. ≤ ρ n−1 ≤ λ n . We now show that ρ i ≤ λ v i + δ. Define L v = P − L v . I v is a diagonal matrix wiht all zero entries except for the j-th diagonal entry, which is at most δ, iff j is conected to v in G, with weight δ. We iterate over ∀i ∈ 1, ..., n − 1. By the Courant-Fischer Theorem [15] we have

Theorem 5.2. Let G be a weighted graph with Laplacian L, eigenvalues λ n ... ≥ λ i ... ≥ λ 1 , and max weight δ. Let L v be the Laplacian of the graph created by deleting some vertex v from G, with eigenvalues λ v n ..

Proof. We have c i = n i=0 λ 2 i − n i=0 λ v2 i . By Theorem 5.1 we have that

. Therefore C e n (G) − C e n (G ′ ) ≤ n n i=0 (2(λ i δ) − δ 2 ). We now need to bound S * C n L ,β . This reduces to an optimization problem. Theorem 5.3. Let G be a weighted graph with Laplacian L, eigenvalues λ n ... ≥ λ i ... ≥ λ 1 , and max weight δ. Let L v be the Laplacian of the graph created by deleting some vertex v from G, with eigenvalues λ v n ..

We know by Wely's theorem [24] that any perturbation P of the original graph G, will perturb the eigenvalues of the Laplacian L of G at most P . If we take the worst case where the perturbation is tight then we have the bound above. If the perturbation is not tight, than the maximum will be reached at a higher θ, and will thus be smaller.

For a given value of β we can obtain the worst case θ by differentiating n n i=0 (2((λ i + θ)δ) − δ 2 )e −βθ = 0, with respect to θ, then solving for θ. Unfortunately, it can be seen that these bounds are likely to be very loose in practice, given their dependence on n, and the sum of the entire spectrum. Experimentally, we find that using these bounds to generate noise destroys all the information about the node ordering that we were seeking to preserve (see Section 7).

Closeness centrality measures how well-connected a user is in a social network. Intuitively, the smaller the sum of the weights along a path between vertices u and v, the better connected they are. It is worth noting that in this interpretation of connectivity the weights represent the cost of traversing an edge. We use paths G (u, v) to denote the set of all paths between u and v in a graph G. The connectivity score between u and v in G, denoted S G (u, v), is thus defined by

Note that a connectivity score is strictly larger than zero, while it could be ∞ if the graph is disconnected. To express the intuition that a low connectivity score makes a vertex more accessible, the closeness centrality score of a vertex u in a graph G, denoted c-score G (u), is defined by

where, by convention, we take 1/∞ = 0.

We use C c n to denote the closeness centrality function with domain G n and co-domain R n defined, for every graph G with totally ordered set of vertices v 1 < · · · < v n , by C c n (G) = (c-score G (v 1 ), c-score G (v 2 ), . . . , c-score G (v n )).

Theorem 6.1. Let G = (V, E, W ) be a graph with |V | = n. The local sensitivity of G with respect to the θ-edge neighbouring relation ∼ and the closeness centrality measure C c n is upper-bounded by

.

Proof. Let G ′ be a graph such that G ∼ G ′ , with G = (V, E, W ) and G ′ = (V, E, W ′ ). Consider two vertices u, v ∈ V , and let the vertex sequence

This means that

as the weight of at most one edge is different, up to a maximum difference of θ, and by definition a shortest path does not go through the same edge twice. Hence |S ′ G (u, v) − S G (u, v)| ≤ θ This gives the following bound:

By the triangle inequality, we also obtain

The following sequence of algebraic development is useful to bound C C n (G)− C C n (G ′ ) 1 :

.

.

Finally, the result follows from the fact that

It is worth remarking that the bound above is tight, as the equality holds for any complete graph of order two such that the weight of its sole edge is greater than θ. We now turn to determining the bounds on smooth sensitivity.

Theorem 6.2. Let G be a graph in G n , w the sum of its weights, and ∼ e θ the θ-edge neighbouring relation with θ > 0. For every positive real β, it holds that

Proof. Take a graph G ′ whose distance to G with respect to ∼ e θ is k. It follows that, if G = (V, E, W ), then G ′ = (V, E, W ′ ) for some weight function W ′ = W . From Theorem 6.1 we obtain that

Now, recall from Definition 3.3 that d(G, G ′ ) = k means that k is the smallest positive integer such that there exists G 0 , . . . , G k ∈ G such that G 0 = G, G k = G ′ and G 0 ∼ e θ · · · ∼ e θ G k . Therefore, it follows that e∈E W (e) − kθ ≤ e∈E W ′ (e). By substituting in Equation 8 we obtain that, if e∈E W (e) − kθ − θ > 0, then,

.

The proof is completed by using the inequality above and the definition of smooth sensitivity. Theorem 6.2 serves as the basis of an algorithmic approach to calculate a bound for smooth sensitivity, which is depicted in Algorithm 1.

Algorithm 1 Given a graph G of order n, and real values θ, ε and β, outputs a randomised algorithm that satisfies ε, 1 e ε √ nβ -differential privacy, if it exists.

1: Let w be the sum of the edge weights in G with w > θ 2:

return Smooth sensitivity is undefined within N. k = k + 1 9: end while 10: Let α = ε 2 11: Let Z be random variable sampled according to h(z) = 1 2 · e −|z| 1 .

Correctness of the algorithm above follows from Lemma 2.5, Example 3 in [18] and the claim that the function f (k) = n×(n−1)×θ (w−kθ)×(w−kθ−θ) · e −βk has a single maximum within the natural numbers domain.

Here we compare the effect on utility of adding noise calibrated to the exact value of local sensitivity, the bounds on local sensitivity enunciated above, and the smooth sensitivity (where possible) for a collection of real-life and synthetic social graphs. The results confirm our theoretical results that the noise needed to provide (ε, δ)-differential privacy has the potential to severely affect utility.

The graphs we have selected are SNAP/p2p-Gnutella05, Wiki-Vote, a synthetic preferential attachment graph, and a synthetic small world graph, created using the Matlab CONTEST toolbox, using O(10 4 ) nodes and the default attachment settings. We generate these graphs one time, and then reuse them throughout our experiments, while the real-life social network graphs can be obtained from the SuiteSparse Matrix Collection [4] . For each graph, we computed the real rankings for the most important 5, 10 and 15 percent of the nodes, and compare this to the differentially private rankings in order to compute the precision of our method. For our experiments, we used ε = 2 and a value of θ equal to the maximum edge weight of the graph under analysis. Certainly, those values are the edge of the maximum privacy that can be offered via differential-privacy, yet they are plausible values for a practical setting. We leave for future work the full analysis of the privacyutility trade-off over the entire domains of ε and θ. We begin our analysis by computing the percentage of correctly identified nodes in the top 5/10/15 percent of the nodes in the perturbed graph using eigenvector centrality. The results are displayed in Table 1 . They show that very few of the important nodes are preserved after perturbation. Although the noise added to the Wiki-Vote graph based on the local sensitivity parameter does not completely destroy the rankings, the precision quickly degrades when using the bound of the local sensitivity. The precision on the other graphs under consideration does not significantly differ from random noise.

In Table 2 we display the experimental results for closeness centrality. In this case, even for local sensitivity, the outputs are dominated by random noise. Finally, we examine the results for Laplacian centrality in Table 3 . Unlike eigenvector and closeness centralities, Laplacian centrality does preserve a statistically significant number of the original nodes in the original ranking when applying noise proportional to local sensitivity. Unfortunately, because the bounds on local and smooth sensitivity for this measure are very loose, we are not able to achieve an accurate differentially private computation in practice. Table 3 : Precision values, in percentages, for Laplacian centrality at the top 5%, 10% and 15% of the rankings.

We have presented the first analysis of the differentially private computation of non trivial centrality measures on weighted graphs. Our study covered eigenvector, Laplacian and closeness centralities. We presented lower and upper bounds on the amount of noise that randomised algorithms based on the smooth sensitivity approach need to add in order to make the output of each measure differentially private. Our results entail that differentially private computation of the three centrality measures via the smooth sensitivity approach is either infeasible, in the sense that there are large families of graphs for which smooth sensitivity is unbounded; or impractical, in the sense that even for the cases where smooth sensitivity is bounded, the required amounts of noise result in unacceptably large utility losses in terms of the quality of centrality-based node rankings.

Publishing community-preserving attributed social graphs with a differential privacy guarantee

Hierarchical structure and the prediction of missing links in networks

Some new bounds on perturbation of subspaces

The university of florida sparse matrix collection

Differential privacy

The algorithmic foundations of differential privacy

Differentially private combinatorial optimization

Accurate estimation of the degree distribution of private networks

Attributed graph models: modeling network structure with correlated attributes

Publishing attributed social graphs with formal privacy guarantees

Unperturbed: spectral analysis beyond davis-kahan

Private analysis of graph structure

Differentially private graphical degree sequences and synthetic graphs

Scalable modeling of real graphs using kronecker multiplication

Note on deleting a vertex and weak interlacing of the laplacian spectrum. ELA. The Electronic Journal of Linear Algebra

A differentially private graph estimator

Detecting communities under differential privacy

Smooth sensitivity and sampling in private data analysis

Sharing graphs using differentially private graph models

Differentially private graph publishing and randomized response for collaborative filtering

Stability and continuity of centrality measures in weighted graphs

Preserving differential privacy in degreecorrelation based graph generation

On learning cluster coefficient of private networks

Das asymptotische Verteilungsgesetz der eigenwerte linearer partieller Differentialgleichungen

Differentially private network data release via structural inference

Private release of graph statistics using ladder functions

Acknowledgements. The work of Yunior Ramírez-Cruz was funded by Luxembourg's Fonds National de la Recherche (FNR), grant C17/IS/11685812 (PrivDA). Part of this article was written while Yunior Ramírez-Cruz was visiting the School of Information Technology at Deakin University.