LinkMirage: Enabling Privacy-preserving Analytics
on Social Relationships
Changchang Liu, Prateek Mittal
Email: cl12@princeton.edu, pmittal@princeton.edu
Department of Electrical Engineering, Princeton University
Social relationships present a critical foundation for many
real-world applications. However, both users and online social
network (OSN) providers are hesitant to share social relationships with untrusted external applications due to privacy
concerns. In this work, we design LinkMirage, a systemthat mediates privacy-preserving access to social relationships.
LinkMirage takes users’ social relationship graph as an input,
obfuscates the social graph topology, and provides untrusted
external applications with an obfuscated view of the social
relationship graph while preserving graph utility.
Our key contributions are (1) a novel algorithm for obfuscating social relationship graph while preserving graphutility, (2) theoretical and experimental analysis of privacy andutility using real-world social network topologies, including
a large-scale Google+ dataset with 940 million links. Our
experimental results demonstrate that LinkMirage provides up
to 10x improvement in privacy guarantees compared to thestate-of-the-art approaches. Overall, LinkMirage enables thedesign of real-world applications such as recommendation systems, graph analytics, anonymous communications, and Sybil
defenses while protecting the privacy of social relationships.
I.

I NTRODUCTION

Online social networks (OSNs) have revolutionized the way
our society interacts and communicates with each other. Under
the hood, OSNs can be viewed as a special graph structurecomposed of individuals (or organizations) and connections
between these entities. These social relationships represent
sensitive relationships between entities, for example, trusted
friendships or important interactions in Facebook, Twitter, orGoogle+, which users want to preserve the security and privacyof.
At the same time, an increasing number of third party applications rely on users’ social relationships (these applications
can be external to the OSN). E-commerce applications canleverage social relationships for improving sales [21], and datamining researchers also rely on the social relationships forfunctional analysis [31], [33]. Social relationships can be used
to mitigate spam [26]. Anonymous communication systems
Permission to freely reproduce all or part of this paper for noncommercial
purposes is granted provided that copies bear this notice and the full citationon the first page. Reproduction for commercial purposes is strictly prohibitedwithout the prior written consent of the Internet Society, the first-named author(for reproduction of an entire paper only), and the author’s employer if thepaper was prepared within the scope of employment.
NDSS ’16, 21-24 February 2016, San Diego, CA, USA
Copyright 2016 Internet Society, ISBN TBD
http://dx.doi.org/10.14722/ndss.2016.23277

can improve client anonymity by leveraging users’ social
relationships [11], [28], [29]. State-of-the-art Sybil defenses
rely on social trust relationships to detect attackers [8], [43].
However, both users and the OSN providers are hesitant toshare social relationships/graphs with these applications due
to privacy concerns. For instance, a majority of users are
exercising privacy controls provided by popular OSNs suchas Facebook, Google+ and LinkedIn to limit access to theirsocial relationships [9]. Privacy concerns arise because external
applications that rely on users’ social relationships can either
explicitly reveal this information to an adversary, or allow
the adversary to perform inference attacks [14], [20], [24],[30], [32], [37]. These concerns hinder the deployment ofmany real-world applications. Thus, there exist fundamentallyconflicting requirements for any link obfuscation mechanism:protecting privacy for the sensitive links in social networks andpreserving utility of the obfuscated graph for use in real-world
applications.
In this work, we design LinkMirage, a system that mediates
privacy-preserving access to social relationships. LinkMirage
takes users’ social relationship graph as an input, either via
an OSN operator or via individual user subscriptions. Next,
LinkMirage obfuscates the social graph topology to protect theprivacy of users’ social contacts (edge/link privacy, not vertex
privacy). LinkMirage then provides external applications suchas graph analytics and anonymity systems [11], [28], [29]with an obfuscated view of the social relationship graph.
Thus, LinkMirage provides a trade-off between securing theconfidentiality of social relationships, and enabling the designof social relationship based applications.
We present a novel obfuscation algorithm that first clusters
social graphs, and then anonymizes intra-cluster links andinter-cluster links, respectively. We obfuscate links in a mannerthat preserves the key structural properties of social graphs.
While our approach is of interest even for static social graphs,
we go a step further in this paper, and consider the evolutionary
dynamics of social graphs (node/link addition or deletion).
We design LinkMirage to be resilient to such evolutionary
dynamics, by consistently clustering social graphs across time
instances. Consistent clustering improves both the privacy andutility of the obfuscated graphs. We show that LinkMirage
provides strong privacy properties. Even a strategic adversary
with full access to the obfuscated graph and prior information
about the original social graph is limited in its ability toinfer information about users’ social relationships. LinkMirage
provides up to 3x privacy improvement in static settings, andup to 10x privacy improvement in dynamic settings comparedto the state-of-the-art approaches.
Overall, our work makes the following contributions.

• First, we design LinkMirage to mediate privacy-preserving
access to users’ social relationships. LinkMirage obfuscateslinks in the social graph (link privacy) and provides untrusted external applications with an obfuscated view ofthe social graph. LinkMirage can achieve a good balance
between privacy and utility, under the context of both staticand dynamic social network topologies.
• Second, LinkMirage provides rigorous privacy guarantees todefend against strategic adversaries with prior informationof the social graph. We perform link privacy analysis boththeoretically as well as using real-world social network
topologies. The experimental results for both a Facebook
dataset (with 870K links) and a large-scale Google+ dataset(with 940M links) show up to 10x improvement in privacy
over the state-of-the-art research.
• Third, we experimentally demonstrate the applicability of
LinkMirage in real-world applications, such as privacypreserving graph analytics, anonymous communication and
Sybil defenses. LinkMirage enables the design of social
relationships based systems while simultaneously protecting
the privacy of users’ social relationships.
• Finally, we quantify a general utility metric for LinkMirage.
We analyze our utility measurement provided by LinkMirage both theoretically and using real-world social graphs(Facebook and Google+).

LinkMirage Server (Trusted)
Obfuscation AlgorithmQ
Original Graph

Obfuscated Graph

G

G¢

LinkMiragesocial link app

Untrusted
Applications

Privacy-preserving graph analysis
Anonymous communication
Vertex anonymity
Sybil defenses...

User1 User2 User3 ĂOSNprovidersQ ( G¢ )Fig. 1. LinkMirage architecture. LinkMirage first collects social link information through our social link app or directly through the OSN providers, andthen applies an obfuscation algorithm to perturb the original social graph(s).
The obfuscated graph(s) would be utilized to answer the query of the untrusted
applications in a privacy-preserving manner. The third-party application (which
queries the social link information) is considered an adversary which aims to
obtain sensitive link information from the perturbed query results.

repeatedly adding perturbations to the output of each graphanalytics algorithm as in differential privacy [12], [13], which
would be rather costly, LinkMirage can obtain the perturbed
graph just once to support multiple graph analytics. Such an
approach protects the privacy of users’ social relationships
from inference attacks using query results. There exists aplethora of attacks against vertex anonymity based mechanisms[20], [30], [32], [37]. Ji et al. [19] recently showed that no
single vertex anonymization technique was able to resist all
the existing attacks. Note that these attacks are not applicableto link privacy schemes. Therefore, a sound approach to vertex
anonymity must start with improvements in our understandingof link privacy. When used as first step in the design of vertex
privacy mechanisms, our approach can protect the privacy ofsocial contacts and graph links even when the vertices are deanonymized using state-of-the-art approaches [20], [30], [32],[37]. Furthermore, our method can even improve the resilienceof vertex anonymity mechanisms against de-anonymization
attacks when applied to unlabelled graphs (will be shown in
Section VI-B).
B. System Architecture and Threat Model
Fig. 1 shows the overall architecture for LinkMirage. For
link privacy, we consider the third-party applications (which
can query the social link information) as adversaries, which
aim to obtain sensitive link information from the perturbed
query results. A sophisticated adversary may have access tocertain prior information such as partial link information of
the original social networks, and such prior information canbe extracted from publicly available sources, social networks
such as Facebook, or other application-related sources as statedin [6]. The adversary may leverage Bayesian inference to infer
the probability for the existence of a link. We assume that
LinkMirage itself is trusted, in addition to the social network
providers/users who provide the input social graph.
In Section V-B, V-C, we define our Bayesian privacy metric(called anti-inference privacy) and an information theoretic
metric (called indistinguishability) to characterize the privacy
offered by LinkMirage against adversaries with prior information. In addition, the evolving social topologies introduce
another serious threat where sophisticated adversaries can
combine information available in multiple query results toinfer users’ social relationships. We define anti-aggregation
privacy in Section V-D, for evaluating the privacy performanceof LinkMirage against such adversaries.
C. Basic Theory
Let us denote a time series of social graphs as G0 , · · · , GT .
For each temporal graph Gt = (Vt , Et ), the set of vertices

II. BACKGROUND
A. Motivating Applications
In this paper, we focus our research on protecting thelink privacy between labeled vertices in social networks [16],[27], [42]. Mechanisms for graph analytics, anonymous communication, and Sybil defenses can leverage users’ social
relationships for enhancing security, but end up revealingusers’ social relationships to adversaries. For example, in the
Tor network [11], the relays’ IP addresses (labels) are alreadypublicly known (vertex privacy in [25], [34], [45] is notuseful). Tor operators are hesitant to utilize social trusts to
set up the Tor circuit as recommended by [28], [29] since
the circuit construction protocol would reveal sensitive social
contact information about the users. Our proposed link-privacy
techniques can thus be utilized by the Tor relay operators toenhance system security while preserving link privacy. Overall,
our work focuses on protecting users’ trust relationships while
enabling the design of such systems.
LinkMirage supports three categories of social relationshipbased applications: 1) Global access to the obfuscated graph:
Applications such as social network based anonymity systems [11], [28], [29] and peer-to-peer networks [8] can utilize
LinkMirage (described in Section IV-B) to obtain a global
view of privacy-preserving social graph topologies; 2) Local
access to the obfuscated graph: an individual user can query
LinkMirage for his/her obfuscated social relationships (local
neighborhood information), to facilitate distributed applications such as SybilLimit [43]; 3) Mediated data analytics:
LinkMirage can enable privacy-preserving data analytics byrunning desired functional queries (such as computing graphmodularity and pagerank score) on the obfuscated graph topology and only returning the result of the query, since immediate
analytics operated on the original graph topology would leaksensitive information about users’ social relationships. Existing
work [12], [13] demonstrated that the implementation of graphanalytics algorithms could leak certain information. Instead of2• LinkMirage also shows significant privacy advantages inanti-aggregation privacy (will be defined in Section V-D),
where the adversary’s estimation for users’ social relationships is less accurate for LinkMirage than the existing
methods.
C. Utility Evaluation

is Vt and the set of edges is Et . For our theoretical analysis,
we focus on undirected graphs where all the |Et | edges are
symmetric, i.e. (i, j) ∈ Et iff (j, i) ∈ Et . Note that our approach can be generalized to directed graphs with asymmetricedges. Pt is the transition probability matrix of the Markov
chain on the vertices of Gt . Pt measures the probability that
we follow an edge from one vertex to another vertex, wherePt (i, j) = 1/deg(i) (deg(i) denotes the degree of vertex i) if(i, j) ∈ Et , otherwise Pt (i, j) = 0. A random walk startingfrom vertex v, selects a neighbor of v at random according to
Pt and repeats the process.

In Section VI, we apply our perturbation algorithm tovarious real world applications such as graph analytics, anonymous communications, and Sybil defenses. Compared to previous methods, LinkMirage results in significantly lower attack
probabilities when applied to anonymous communications andhigher resilience to de-anonymization attacks when applied
to vertex anonymity systems. LinkMirage even surprisingly
improves the Sybil detection performance when applied to the
distributed SybilLimit systems. LinkMirage also outperform
existing methods in preserving the utility for multiple graphanalytics applications, such as pagerank score and modularity.
In Section VII, we further analyze LinkMirage’s ability topreserve general graph-theoretic characteristics.

III. S YSTEM OVERVIEW AND ROADMAP
A. LinkMirage System
Our objective for LinkMirage is to obfuscate social relationships to strike a balance between privacy for users’social relationships and the usability for large-scale realworld applications, as will be discussed in Section IV-A. We
deploy LinkMirage as a Facebook application that implements
graph construction and obfuscation, as will be discussed in
Section IV-B.
For our perturbation mechanism of LinkMirage, we take
both the static and the temporal social network topology
into consideration, as will be discussed in Section IV-C. Our
obfuscation mechanism consists of the following conceptual
steps:• Dynamic clustering which finds community structures in
evolving graphs by simultaneously considering consecutive
graphs. Our dynamic clustering utilizes an effective backtracking strategy to cluster a graph based on the clusteringresult of the previous graph.
• Selective perturbation which perturbs the minimal amountof edges in the evolving graphs according to the dynamic
clustering result, where we only perturb the changed communities between consecutive graphs. In this manner, it
is possible to use a very high privacy parameter in theperturbation process, while preserving structural propertiesof the social network topologies.
We further discuss the scalability of our perturbation algorithm on the real world large-scale Google+ dataset in Section IV-D and visually show the effectiveness of our algorithm
on the real world Facebook dataset in Section IV-E.

IV.
A. Design Goals

L INK M IRAGE S YSTEM

We envision that applications relying on social relationships
between users can bootstrap this information from onlinesocial network operators such as Facebook, Google+, Twitter with access to the users’ social relationships. To enable
these applications in a privacy-preserving manner, a perturbedsocial graph topology (by adding noise to the original graphtopology) should be available.
Social graphs evolve over time, and the third-party applications would benefit from access to the most current versionof the graph. A baseline approach is to perturb each graphsnapshot independently. However, the sequence of perturbed
graphs provide significantly more observations to an adversary
than just a single perturbed graph. We argue that an effective
perturbation method should consider the evolution of theoriginal graph sequence. Therefore, we have the overall design
goals for our system as:1) We aim to obfuscate social relationships while balancing
privacy for users’ social relationships and the usability forreal-world applications.
2) We aim to handle both the static and dynamic social
network topologies.
3) Our system should provide rigorous privacy guarantees
to defend against adversaries who have prior informationof the original graphs, and adversaries who can combine
multiple released graphs to infer more information.
4) Our method should be scalable to be applied in real-world
large-scale social graphs.

B. Privacy Evaluation
In Section V, we rigorously analyze the privacy advantage
of our LinkMirage over the state-of-the-art approaches, byconsidering three adversarial scenarios where sophisticatedadversaries can combine information available in multiple
query results to infer users’ social relationships. The privacy
advantage of our LinkMirage will be demonstrated as• LinkMirage shows significant privacy advantages in antiinference privacy (will be defined in Section V-B). The
difference between the posterior probability and the priorprobability of the existence of an link is smaller for LinkMirage than the state-of-the-art methods.
• LinkMirage achieves higher indistinguishability from an
information theoretic perspective (will be defined in Section V-C) where the obfuscated graph of LinkMirage contains less information of users’ social relationships than thestate-of-the-art methods.

B. LinkMirage: Deployment
To improve the usability of our proposed obfuscation approach (which will be described in detail in
Section IV-C), and to avoid dependance on the OSN
providers, we developed a Facebook application (available:
https://apps.facebook.com/linkmirage/) that implements graphconstruction (via individual user subscriptions) and obfuscation. The work flow of the LinkMirage deployment is as follows: (i) When a user visits the above URL, Facebook checks
the credentials of the user, asks whether to grant the user’s
3

friends permission, and then gets redirected to the application
hosting server. (ii) The application server authenticates itself,
and then queries Facebook for the information of the user’s
friends, and returns their information such as user’s id. The
list of user’s friends can then be collected by the application
server to construct a Facebook social graph for the current
timestamp. Leveraging LinkMirage, a perturbed graph for thistimestamp would be available which preserves the link privacyof the users’ social relationships.
Real-world systems such as Uproxy, Lantern, Kaleidoscope[17], anonymity systems [11], [28], [29], Sybil defenses systems [8], [43] can directly benefit from our protocol throughautomatically obtaining the perturbed social relationships. Furthermore, our protocol can enable privacy-preserving graphanalytics for OSN providers.

3. evolution

Gt -1

Gt

1. clustering

4. dynamic clustering

C1

C1
C2

2. perturbation

Gt¢-1

C3
C2

5. selective perturbation

C¢3

C¢1

C¢1

C¢2

G¢t

C¢2

Fig. 2. Our perturbation mechanism for Gt . Assume that Gt−1 has alreadybeen dynamically obfuscated, based on dynamic clustering (step 1) andselective perturbation (step 2). Our mechanism analyzes the evolved graph
Gt (step 3) and dynamically clusters Gt (step 4) based on the freed m hopneighborhood (m = 2) of new links (between green and blue nodes), themerging virtual node (the large red node in step 4), and the new nodes. By
comparing the communities in Gt−1 and Gt , we can implement selective
perturbation (step 5), i.e. perturb the changed blue community independently
and perturb the unchanged red and green communities in the same way as
G0t−1 , and then perturb the inter-cluster links.

C. LinkMirage: Perturbation Algorithm
Social networks evolve with time and publishing a timeseries of perturbed graphs raises a serious privacy challenge:an adversary can combine information available from multiple
perturbed graphs over time to compromise the privacy of users’social contacts [5], [10], [38]. In LinkMirage, we take a timeseries of graph topologies into consideration, to account for
the evolution of the social networks. Intuitively, the scenario
with a static graph topology is just a special situation of thetemporal graph sequence, and is thus inherently incorporated
in our model.
Consider a social graph series G0 = (V0 , E0 ),· · · ,GT =(VT , ET ). We want to transform the graph series to G00 =(V0 , E00 ),· · · ,G0T = (VT , ET0 ), such that the vertices in G0t
remain the same as in the original graph Gt , but the edges are
perturbed to protect link privacy. Moreover, while perturbing
the current graph Gt , LinkMirage has access to the past graphs
in the time series (i.e., G0 , · · · , Gt−1 ). Our perturbation goal is
to balance the utility of social graph topologies and the privacyof users’ social contacts, across time.
Approach Overview: Our perturbation mechanism for
LinkMirage is illustrated in Fig. 2.
Static scenario: For a static graph Gt−1 , we first cluster
it into several communities, and then perturb the links withineach community. The inter-cluster links are also perturbed toprotect their privacy.
Dynamic scenario: Let us suppose that Gt evolves from
Gt−1 by addition of new vertices (shown in blue color). To
perturb graph Gt , our intuition is to consider the similarity
between graphs Gt−1 and Gt .
First, we partition Gt−1 and Gt into subgraphs, by clustering
each graph into different communities. To avoid randomness(guarantee consistency) in the clustering procedure and to
reduce the computation complexity, we dynamically cluster thetwo graphs together instead of clustering them independently.
Noting that one green node evolves by connecting with a newblue node, we free 1 all the nodes located within m = 2 hops ofthis green node (the other two green nodes and one red node)and merge the remaining three red nodes to a big virtual node.
Then, we cluster these new nodes, the freed nodes and theremaining virtual node to detect communities in Gt .
Next, we compare the communities within Gt−1 and Gt ,and identify the changed and unchanged subgraphs. For theunchanged subgraphs C1 , C2 , we set their perturbation attime t to be identical to their perturbation at time t − 1,denoted by C10 , C20 . For the changed subgraph C3 , we perturb it
independently to obtain C30 . We also perturb the links between
communities to protect privacy of these inter-cluster links.
Finally, we publish G0t as the combination of C10 , C20 , C30 andthe perturbed inter-cluster links. There are two key steps in
our algorithm: dynamic clustering and selective perturbation,
which we describe in detail as follows.
1) Dynamic Clustering: Considering that communities insocial networks change significantly over time, we need toaddress the inconsistency problem by developing a dynamic
community detection method. Dynamic clustering aims to findcommunity structures in evolving graphs by simultaneously
considering consecutive graphs in its clustering algorithms.
There are several methods in the literature to cluster evolving
graphs [3], but we found them to be unsuitable for use
in our perturbation mechanism. One approach to dynamic
clustering involves performing community detection at eachtimestamp independently, and then establishing relationships
between communities to track their evolution [3]. We foundthat this approach suffers from performance issues induced byinherent randomness in clustering algorithms, in addition to
the increased computational complexity.
Another approach is to combine multiple graphs into asingle coupled graph [3]. The coupled graph is constructed byadding edges between the same nodes across different graphs.
Clustering can be performed on the single coupled graph. We
found that the clustering performance is very sensitive to theweights of the added links, resulting in unstable clusteringresults. Furthermore, the large dimensionality of the coupledgraph significantly increases the computational overhead.
For our perturbation mechanism, we develop an adaptive
dynamic clustering approach for clustering the graph Gt using
the clustering result for the previous graph Gt−1 . This enables
our perturbation mechanism to (a) exploit the link correlation/similarity in consecutive graph snapshots, and (b) reduce
computation complexity by avoiding repeated clustering forunchanged links.
Clustering the graph Gt from the clustering result of the

1 We free the nodes from the previously clustering hierarchy.

4TABLE I. Temporal Statistics of the Facebook Dataset.
Time# of nodes# of edges
Average degree

09,586
48,966
5.11

1
9,719
38,0583.91

2
11,64947,0244.03

313,84854,7873.96

4
14,21049,7443.50

516,34458,0993.55

618,97465,604
3.46

726,22097,0953.70

835,048142,274
4.06

Algorithm 1 LinkMirage, with dynamic clustering (steps
1-2) and selective perturbation (steps 3-6). The parameterk denotes the perturbation level for each community.
Here, ch, un, in are short for changed, unchanged, intercommunity, respectively.
Input: {Gt , Gt−1 , G0t−1 } if t ≥ 1 or {Gt } if t = 0;
Output: G0t ;G0t , Ct =null;
if t=0;cluster G0 to get C0 ;label C0 as changed, i.e. C0−ch = C0 ;endif/*Begin Dynamic Clustering*/
1. free the nodes within m hops of the changed links;
2. re-cluster the new nodes, the freed nodes, the remai-ning merged virtual nodes in C(t−1) to get Ct ;/*End Dynamic Clustering*//*Begin Selective Perturbation*/
3. find the unchanged communities Ct−un and the chan-ged communities Ct−ch ;4. let G0t−un = G0(t−1)−un ;5. perturb Ct−ch for G0t−ch by the static method;
6. foreach community pair a and b;
if both of the communities belong to Ct−un
0
0
Ct−in
(a, b) = C(t−1)−in(a, b);
else
foreach marginal node va (i) in a and vb (j) in b
randomly add an edge (va (i), vb (j)) with pro(i)) deg(vb (j))|va |-bability deg(v|Eaab
to G0t−in (a, b);|(|va |+|vb |)/*End Selective Perturbation*/
return G0t = [G0t−ch , G0t−un , G0t−in ];previous graph Gt−1 requires a backtracking strategy. We use
the maximum-modularity method [31] for clustering, which ishierarchical and thus easy to backtrack. Our backtrack strategy
is to first maintain a history of the merge operations that led tothe current clustering. When an evolution occurs, the algorithm
backtracks over the history of merge operations, in order toincorporate the new additions and deletions in the graph.
More concretely, if the link between node x and node
y is changed (added or deleted), we omit all the m-hop
neighborhoods of x and y as well as x and y themselvesfrom the clustering result of the previous timestamp, and thenperform re-clustering. All the new nodes, the changed nodes
and their m-hop neighbors, and the remaining merged nodes
in the previous clustering result would be considered as basic
elements for clustering Gt (recall Figure 2).
For efficient implementation, we store the intermediate
results of the hierarchical clustering process in a data structure.
Upon link changes between x, y, we free the m-hop neighborhood of x, y from the stored data structure.
2) Selective perturbation:
Intra-cluster Perturbation: After clustering Gt based on
Gt−1 using our dynamic clustering method, we perturb Gt
based on Gt−1 and the perturbed G0t−1 . First, we compare
the communities detected in Gt−1 and Gt , and classify themas changed or unchanged. Our unchanged classification does
not require that the communities are exactly the same, butthat the overlap among vertices/links exceeds a threshold. Our
key idea is to keep the perturbation process for links in theunchanged communities to be identical to their perturbationin the previous snapshot. In this manner, we can preserve
the privacy of these unchanged links to the largest extent;
it is easy to see that alternate approaches would leak more
information. For the communities which are classified aschanged, our approach is to perturb their links independentlyof the perturbation in the previous timestamp. For independent
perturbations, we leverage the static perturbation method of
Mittal et al. in [27]. Their static perturbation deletes all theedges in the original graph, and replaces each edge (v, u)with a fake edge (v, w) selected from the k-hop random walkstarting from v. Larger perturbation parameter k corresponds
to better privacy and leads to worse utility.
Inter-cluster Perturbation: Finally, we need to interconnect
the subgraphs identified above. Suppose that |va | nodes and|vb | nodes are connecting communities a and b respectively,
and they construct an inter-community subgraph. For eachmarginal node va (i) ∈ va and vb (j) ∈ vb (here the marginal
node in community a (resp.b) refers to the node that has neighbors in the other community b (resp.a)) , we randomly connect(i)) deg(vb (j))|va | 2
them with probability deg(v|Eaab. Here, all the|(|va |+|vb |)computations for deg(·), |v· (·)|, |E· | only consider the marginal
nodes. We can combine the perturbed links corresponding to

the unchanged communities, changed communities, and intercommunity subgraphs, to compute the output of our algorithm,
i.e., G0t .
LinkMirage not only preserves the structural characteristicsof the original graph series, but also protects the privacy of
the users by randomizing the original links. As compared toprior work, our method provides stronger privacy and utility
guarantees for evolving graphs. Detailed procedures are statedin Algorithm. 1.
LinkMirage improves the state-of-the-art methods such as[27] by incorporating the temporal graph topology. Surprisingly, our approach of first isolating communities and thenselectively perturbing them provides benefits even in a static
context! This is because previous static approaches use a single
parameter to control the privacy/utility trade-off. Thus, if we
apply them to the whole graph using high privacy parameters,
it would destroy graph utility (e.g. community structures). On
the other hand, LinkMirage applies perturbations selectively tocommunities; thus it is possible to use a very high privacy parameter in the perturbation process, while preserving structural

2 This probability is set for the preservation of degree distributions as
analyzed in Section VII.

5

OriginalgraphsMittal et al.
(k=5)

Mittal et al.
(k=20)

LinkMirage(k=5)

LinkMirage(k=20)

t=3
OriginalgraphsMittal et al.
(k=5)

Mittal et al.
(k=20)

LinkMirage(k=5)

LinkMirage(k=20)

t=4

t=5

Fig. 3. Dynamic Facebook interaction dataset topology, for t = 3, 4, 5. On the left, we can see that LinkMirage has superior utility than the baseline approach(Mittal et al.), especially for larger values of k (due to dynamic clustering). On the right, we show the overlapped edges (black) and the changed edges (yellow)
between consecutive graphs: t=(3, 4) and t=(4, 5). We can see that in LinkMirage, the perturbation of unchanged communities is correlated across time (selective
perturbation), minimizing information leakage and enhancing privacy.

algorithm results in the loss of structure properties, and appears
to resemble a random graph. Thus, our approach of firstisolating communities and applying perturbation at the levelof communities has benefits even in a static context.
Fig. 3 also shows the privacy benefits of our perturbation
algorithm for timestamps t = 4, 5. We can see that LinkMirage
reuses perturbed links (shown as black unchanged links) in
the unchanged communities (one unchanged community fort = 4 and two unchanged communities for t = 5). Therefore,
LinkMirage preserves the privacy of users’ social relationships
by considering correlations among the graph sequence, and thisbenefit does not come at the cost of utility. In the following
sections, we will formally quantify the privacy and utility
properties of LinkMirage.

properties such as community structures.
D. Scalable Implementation
Our algorithm relies on two key graph theoretical techniques: community detection (serves as a foundation for the
dynamic clustering step in LinkMirage) and random walk
(serves as a foundation for the selective perturbation step in
LinkMirage). The computational complexity for both community detection and random walk is O(|Et |) [3], [27] where|Et | is the number of edges in graph Gt , therefore theoverall computational complexity of our approach is O(|Et |).
Furthermore, our algorithms are parallelizable. We adopt theGraphChi parallel framework in [22] to implement our algorithm efficiently using a commodity workstation (3.6 GHz,
24GB RAM). Our parallel implementation scales to very largesocial networks; for example, the running time of LinkMirage
is less than 100 seconds for the large scale Google+ dataset(940 million links) (will be described in Section V-A) using
our commodity workstation.

V.

P RIVACY A NALYSIS

We now address the question of understanding link privacy of LinkMirage. We propose three privacy metrics: antiinference privacy, indistinguishability, anti-aggregation privacy to evaluate the link privacy provided by LinkMirage.
Both theoretical analysis and experimental results with a Facebook dataset (870K links) and a large-scale Google+ dataset(940M links) show the benefits of LinkMirage over previous
approaches. We also illustrate the relationship between our
privacy metric and differential privacy.

E. Visual Depiction
For our experiments, we consider a real world Facebook
social network dataset [40] among New Orleans regional
network, spanning from September 2006 to January 2009.
Here, we utilize the wall post interaction data which represents
stronger trust relationships and comprises of 46,952 nodes(users) connected by 876,993 edges. We partitioned the dataset
using three month intervals to construct a total of 9 graphinstances as shown in Table I. Fig. 3 depicts the outcome ofour perturbation algorithm on the partitioned Facebook graphsequence with timestamp t = 3, 4, 5 (out of 9 snapshots),for varying perturbation parameter k (perturbation parameterfor each community). For comparative analysis, we consider
a baseline approach [27] that applies static perturbation foreach timestamp independently. In the dynamic clustering stepof our experiments, we free the two-hop neighborhoods of thechanged nodes, i.e. m = 2.
The maximum-modularity clustering method yields two
communities for G3 , three communities for G4 , and fourcommunities for G5 . For the perturbed graphs, we use thesame color for the vertices as in the original graph andwe can see that fine-grained structures (related to utility)
are preserved for both algorithms under small perturbation
parameter k, even though links are randomized. Even for highvalues of k, LinkMirage can preserve the macro-level (suchas community-level) structural characteristics of the graph. On
the other hand, for high values of k, the static perturbation

A. Experimental Datasets
To illustrate how the temporal information degrades privacy,
we consider two social network datasets. The first one is alarge-scale Google+ dataset [14]. whose temporal statistics areillustrated in Table II. To the best of our knowledge, this is thelargest temporal dataset of social networks in public domain.
The Google+ dataset is crawled from July 2011 to October
2011 which has 28,942,911 nodes and 947,776,172 edges.
The dataset only considers link additions, i.e. all the edges in
the previous graphs exist in the current graph. We partitioned
the dataset into 84 timestamps. The second one is the 9timestamp Facebook wall posts dataset [40] as we stated in
Section IV-E. with temporal characteristics shown in Table I. It
is worth noting that the wall-posts data experiences tremendous
churn with only 45% overlap for consecutive graphs. Since ourdynamic perturbation method relies on the correlation between
consecutive graphs, the evaluation of our dynamic method on
the Facebook wall posts data is conservative. To show the
improvement in performance of our algorithm for graphs thatevolve at a slower rate, we also consider a sampled graph
6

TABLE II. Temporal Statistics of the Google+ Dataset.

1
0.8
0.6

Cumulative distribution function

Cumulative distribution function

Time
Jul.29Aug.8
Aug.18Aug.28
Sep.7
Sep.17
Sep.27
Oct.7# of nodes
16,165,781 17,483,936 17,850,948 19,406,327 19,954,197 24,235,387 28,035,472 28,942,911# of edges
505,527,124 560,576,194 575,345,552 654,523,658 686,709,660 759,226,300 886,082,314 947,776,172
Average degree
31.271432.0624
32.230533.7273
34.4143
31.3272
31.6058
32.7464

Prior probability
k=5, Mittal et al.
k=5, LinkMirage
k=20, Mittal et al.
k=20, LinkMirage

0.4
0.2
0 −3
10

10

−2

−1

10

0

10

(a) Inference Probability

1

Prior probability
k=5, Mittal et al.
k=5, LinkMirage
k=20, Mittal et al.
k=20, LinkMirage

0.8
0.6
0.4
0.2
0 −3
10

10

−2

−1

0

10

10

(b) Inference probability

Fig. 4. (a),(b) represent the link probability distributions for the whole Facebook interaction dataset and the sampled Facebook interaction dataset with 80%
overlap. We can see that the posterior probability of LinkMirage is more similar to the prior probability than the baseline approach.

sequence extracted from the Facebook wall posts data with
80% overlap for consecutive graphs.

Cumulative distribution function

1

B. Anti-Inference Privacy
First, we consider adversaries that aim to infer link information by leveraging Bayesian inference. We define theprivacy of a link Lt (or a subgraph) in the t-th graph instance,as the difference between the posterior probability and theprior probability of the existence of the link (or a subgraph),
computed by the adversary using its prior information W ,and the knowledge of the perturbed graph sequence {G0i }ti=0 .
Utilizing Bayesian inference, we have

0.8
0.7

Prior Probability
k=5, Mittal et al.
k=5, LinkMirage
k=20, Mittal et al.
k=20, LinkMirage

0.6
0.5
0.4
0.3
0.2
0.1
0 −3
10

−2

10

10

−1

0

10

Inference Probability

Fig. 5. Link probability distribution for the Google+ dataset under theadversary’s prior information extracted from the social-attribute network modelin [14].

and Lt = 1 denotes the existence of this link while Lt = 0
denotes the non-existence of this link). Such prior information
can be extracted from personal public information, Facebook
related information or other application-related information as
stated in [6]. Note that this is a very strong adversarial prior,which would lead to the worst-case analysis of link privacy.
e i (Lt )}t
Denoting {Gi=0 as the prior which contains all theinformation except Lt , we have the posterior probability oflink Lt under the worst case isDefinition 1: For link Lt in the original graph sequence
G0 , · · · , Gt and the adversary’s prior information W , the antiinference privacy Privacyai for the perturbed graph sequence
G00 , · · · , G0t is evaluated by the similarity between the posterior probability P (Lt |{G0i }ti=0 , W ) and the prior probability
P (Lt |W ), where the posterior probability is
P (Lt |{G0i }ti=0 , W ) =0.9

P ({G0i }ti=0 |Lt , W ) × P (Lt |W )(1)
P ({G0i }ti=0 |W )e i (Lt )}ti=0 )P (Lt |{G0i }ti=0 , {Ge i (Lt )}ti=0 )e i (Lt )}ti=0 ) × P (Lt |{G
P ({G0i }ti=0 |, Lt , {G=e i (Lt )}t )P ({G0i }ti=0 |{Gi=0Higher similarity implies better anti-inference privacy.
The difference between the posterior probability and the priorprobability represents the information leaked by the perturbation mechanism. Similar intuition has been mentioned in [23].
Therefore, the posterior probability should not differ muchfrom the prior probability.
In the above expression, P (Lt |W ) is the prior probabilityof the link, which can be computed based on the known
structural properties of social networks, for example, by using
link prediction algorithms [24]. Note that P ({G0i }ti=0 |W ) is anormalization constant that can be analyzed by sampling techniques. The key challenge is to compute P ({G0i }ti=0 |Lt , W )3 .
For evaluation, we consider a special case where the adversary’s prior is the entire time series of original graphs except
the link Lt (which is the link we want to quantify privacy for,where
e i (Lt )}ti=0 ) = P (G00 |G
e 0 (Lt ))×
P ({G0i }ti=0 |Lt , {G
0
0 e
0
0
e 1 (Lt )) · · · P (Gt |Gt−1 , G
e t−1 (Lt ), G
e t (Lt ))P (G1 |G0 , G0 (Lt ), G

Therefore, the objective of perturbation algorithms is to makee i (Lt )}t ) close to P (Lt |{G
e i (Lt )}t ).
P (Lt |{G0i }ti=0 , {Gi=0i=0Comparison with previous work: Fig. 4 shows the posterior probability distribution for the whole Facebook graphsequence and the sampled Facebook graph sequence with
80% overlapping ratio, respectively. We computed the priorprobability using the link prediction method in [24]. We cansee that the posterior probability corresponding to LinkMirage
is closer to the prior probability than that of the method of
Mittal et al. [27]. In Fig. 4(b), taking the point where thelink probability equals 0.1, the distance between the posterior
CDF and the prior CDF for the static approach is a factor of 3

3 The detailed process for computing the posterior probability can be foundin [27].

7k=5, Mittal et al.
k=5, LinkMirage
k=20, Mittal et al.
k=20, LinkMirage
Hay’s et al.

0.4
0.3
0.2

0.4
0.3
0.2
0.1

0.1
0
0

k=5, Mittal et al.
k=5, LinkMirage
k=20, Mittal et al.
k=20, LinkMirage
Hay et al.

0.5

Indistinguishability

Indistinguishability

0.5

1

2

3

4

5

(a) Timestamp t

6

7

0
0

8

1

2

3

4

5

(b) Timestamp t

6

7

8

Fig. 6. (a),(b) represent the temporal indistinguishability for the whole Facebook interaction dataset and the sampled Facebook interaction dataset with 80%
overlap. Over time, the adversary has more information, resulting in decreased indistinguishability. We can also see that LinkMirage has higher indistinguishability
than the static method and the Hay’s method in [16], although it still suffers from some information leakage.

larger than LinkMirage (k = 20). Larger perturbation degree
k improves privacy and leads to smaller difference with theprior probability. Finally, by comparing Fig. 4(a) and (b), we
can see that larger overlap in the graph sequence improves theprivacy benefits of LinkMirage. We also compare with thework of Hay et al. in [16], which randomizes the graph withr real links deleted and another r fake links introduced. The
probability for a real link to be preserved in the perturbed graphis 1 − r/m, which should not be small otherwise the utility
would not be preserved. Even considering r/m = 0.5 (which
would substantially hurt utility [16]), the posterior probability
for a link using the method of Hay et al. would be 0.5,
even without prior information. In contrast, our analysis for
LinkMirage considers a worst-case prior, and shows that theposterior probability is smaller than 0.5 for more than 50% of
the links when k = 20 in Fig. 4. Therefore, our LinkMirage
provides significantly higher privacy than the work of Hay etal.
Adversaries with structural and contextual information:
Note that our analysis so far focuses on quantifying linkprivacy under an adversary with prior information about theoriginal network structure (including link prediction capabilities). In addition, some adversaries may also have access tocontextual information about users in the social network, suchas user attributes, which can also be used to predict network
links (e.g., social-attribute network prediction model in [14]).
We further computed the prior probability using such socialattribute network prediction model in [14] and showed the linkprobability for the Google+ dataset in Fig. 5. The posterior
probability of our LinkMirage is closer to the prior probability
and thus LinkMirage achieves better privacy performance thanprevious work.

Definition 2: The indistinguishability for a link Lt in
the original graph Gt that the adversary can inferfrom the perturbed graph G0t under the adversary’s priore i (Lt )}t
information {G=i=0 is defined as Privacyid0 te i (Lt )}t ).
H(Lt |{Gi }i=0 , {Gi=0
Furthermore, we quantify the behavior of indistinguishability
over time. For our analysis, we continue to consider the worst
case prior of the adversary knowing the entire graph sequence
except the link Lt . To make the analysis tractable, we add
another condition that if the link L exists, then it exists inall the graphs (link deletions are rare in real world social
networks). For a large-scale graph, only one link would notaffect the clustering result. Then, we have
Theorem 1: The indistinguishability decreases with time,e i (L)}ti=0 ) ≥ H(L|{G0i }t+1 , {Ge i (L)}t+1 )H(L|{G0i }ti=0 , {G
i=0
i=0
(2)
The inequality follows from the theorem conditioning reduces
entropy in [7]. Eq.2 shows that the indistinguishability would
not increase as time evolves. The reason is that over time,
multiple perturbed graphs can be used by the adversary toinfer more information about link L.
Next, we theoretically show why LinkMirage has better
privacy performance than the static method. For each graph
Gt , denote the perturbed graphs using LinkMirage and thestatic method as G0t , G0,st , respectively.
Theorem 2: The indistinguishability for LinkMirage isgreater than that for the static perturbation method, i.e.
e i (Lt )}ti=0 ) ≥ H(Lt |{G0,s }ti=0 , {Ge i (Lt )}ti=0 )H(Lt |{G0i }ti=0 , {Gi(3)Proof: In LinkMirage, the perturbation for the current
graph Gt is based on perturbation for Gt−1 . Let us denotethe changed subgraph between Gt−1 , Gt as Gt−ch , thenC. Indistinguishability
Based on the posterior probability of a link under the worst
e i (Lt )}t ), we need to qualify the pricase P (Lt |{G0i }ti=0 , {Gi=0vacy metric for adversaries who aim to distinguish the posterior
probability with the prior probability. Since our goal is to
reduce the information leakage of Lt based on the perturbed
e i (Lt )}t , wegraphs {G0i }ti=0 and the prior knowledge {Gi=0
consider the metric of indistinguishability to quantify privacy,
which can be evaluated by the conditional entropy of a private
message given the observed variables [7]. The objective foran obfuscation scheme is to maximize the indistinguishabilityof the unknown input I given the observables O, i.e. H(I|O)(where H denotes entropy of a variable [7]). Here, we define
our metric for link privacy ase i (Lt )}ti=0 )H(Lt |{G0i }ti=0 , {G
0
0
0
0,s
t
e
=H(Lt |{G0i }t−2i=0 , Gt−1 , Gt − Gt−ch , Gt−ch , {Gi (Lt )}i=0 )
0 t−1
0,s
t
e i (Lt )}i=0 )=H(Lt |{Gi }i=0 , G
, {G
t−ch

0,s
t
e
≥H(Lt |{G0i }t−1i=0 , Gt , {Gi (Lt )}i=0 )e i (Lt )}ti=0 )≥H(Lt |{G0,s }ti=0 , {Giwhere the first inequality also comes from the theorem conditioning reduces entropy in [7]. The second inequality generalizes the first inequality from a snapshot t to the entire sequence.
From Eq.3, we can see that LinkMirage may offer superior8indistinguishability compared to the static perturbation, andthus provides higher privacy.

privacy and the estimation error as (we defer the proofs to the
Appendix to improve readability.)

Comparison with previous work: Next, we experimentally
analyze our indistinguishability metric over time. Fig. 6 depicts
the indistinguishability metric using the whole Facebook graphsequence and the sampled Facebook graph sequence with 80%
overlap. We can see that the static perturbation leaks more
information over time. In contrast, the selective perturbationachieves significantly higher indistinguishability. In Fig. 6(a),after 9 snapshots, and using k = 5, the indistinguishabilityof the static perturbation method is roughly 1/10 of theindistinguishability of LinkMirage. This is because selective
perturbation explicitly takes the temporal evolution into consideration, and stems privacy degradation via the selective
perturbation step. Comparing Fig. 6(a) and (b), LinkMirage
has more advantages for larger overlapped graph sequence.
We also compare with the work of Hay et al. in [16], For the
first timestamp, the probability for a real link to be preservedin the anonymized graph is 1 − r/m. As time evolves, theprobability would decrease to (1 − r/m)t . Combined with theprior probability, the corresponding indistinguishability for the
method of Hay et al. is shown as the black dotted line in
Fig. 6, which converges to 0 very quickly (we also consider
r/m = 0.5 which would substantially hurt utility [16])Compared with the work of Hay et al, LinkMirage significantly
improves privacy performance. Even when t = 1, LinkMiragewith k = 20 achieves up to 10x improvement over theapproach of Hay et al. in the indistinguishability performance.

Theorem 3: The anti-aggregation privacy is a lower boundof the estimation error for the adversaries, andkPtk − Pt0 kTV ≤ kkPt − P̂t kTV(4)

We further consider the network evolution where the adversary
can combine all the perviously perturbed graphs together toextract more k-hop information of the current graph. Under
this situation, a strategic methodology for the adversary is tocombine the perturbed graph series G00 , · · S· , G0t , to construct00
a new perturbed graph Ğt , where Ğt = i=0,1··· ,t G0i . The
combined perturbed graph Ğ0t contains more information about
the k-hop graph Gkt than G0t . Correspondingly, the transition
probability matrix P̆t0 of the combined perturbed graph Ğ0t
would provide more information than Pt0 . That is to say, theanti-aggregation privacy decreases with time.
Comparison with previous work: We evaluate the antiaggregation privacy of LinkMirage on both the Google+
dataset and the Facebook dataset. Here we perform our experiments based on a conservative assumption that a link always
exists after it is introduced. The anti-aggregation privacy
decreases with time since more information about the k-hop
neighbors of the graph is leaked as shown in Fig. 7. Our
selective perturbation preserves correlation between consecutive graphs, therefore leaks less information and achieves
better privacy than the static baseline method. For the Google+
dataset, the anti-aggregation privacy for the method of Mittal
et al. is only 1/10 of LinkMirage after 84 timestamps.

D. Anti-aggregation Privacy
Next, we consider the adversaries who try to aggregate all
the previously published graphs to infer more information.
Recall that after community detection in our algorithm, we
anonymize the links by leveraging the k-hop random walk.
Therefore, the perturbed graph G0 is actually a sampling of
the k-hop graph Gk , where the k-hop graph Gk represents
graph where all the k-hop neighbors in the original graphare connected. It is intuitive that a larger difference between
Gk and G0 represents better privacy. Here, we utilize thedistance between the corresponding transition probability matrices kPtk − Pt0 kTV 4 to measure this difference. And we
extend the definition of total variance [18] from vector tomatrix by averaging total variance P
distance of each row in the|Vt |matrix, i.e. kPtk − Pt0 kTV = |V1t | v=1
kPtk (v) − Pt0 (v)kTV ,k0
where Pt (v), Pt (v) denotes the v-th row of Ptk , Pt0 . We thenformally define the anti-aggregation privacy as

E. Relationship with Differential Privacy
Our anti-inference privacy analysis considers the worstcase adversarial prior to infer the existence of a link in thegraph. Next, we uncover a novel relationship between this antiinference privacy and differential privacy.
Differential privacy is a popular theory to evaluate theprivacy of a perturbation scheme [12], [13]. The frameworkof differential privacy defines local sensitivity of a query
function f on a dataset D1 as the maximal |f (D1 ) − f (D2 )|1
for all D2 differing from D1 in at most one element df =maxD2 kf (D1 ) − f (D2 k1 . Based on the theory of differential
privacy, a mechanism that adds independent Laplacian noisewith parameter df / to the query function f , satisfies differential privacy. The degree of added noise, which determines the utility of the mechanism, depends on the local
sensitivity. To achieve a good utility as well as privacy,
the local sensitivity df should be as small as possible. The
following lemma demonstrates the effectiveness of our worstcase Bayesian analysis by showing that the objective for goodutility-privacy balance under our worst-case Bayesian analysis
is equivalent to that under differential privacy.

Definition 3: The anti-aggregation privacy for a perturbed
graph G0t with respect to the original graph Gt and the perturbation parameter k is Privacyaa (Gt , G0t , k) = kPtk − Pt0 kTV .
The adversary’s final objective is to obtain an estimatedmeasurement of the original graph, e.g. the estimated transition
probability matrix P̂t which satisfies P̂tk = Pt0 . A straightforward manner to evaluate privacy is to compute the estimation
error of the transition probability matrix i.e. kPt − P̂t kTV .
We can derive the relationship between the anti-aggregation

Remark 1: The requirement for good utility-privacy balancein differential privacy is equivalent to the objective of ourBayesian analysis under the worst case. (We defer the proofs
to Appendix to improve readability.)

4 We choose the total variance distance to evaluate the statistical distance
between Ptk and Pt0 as in [27].

91Anti−aggregation Privacy

Anti−aggregation Privacy

1
0.8
0.6
0.4

K=2,Mittal et al.
K=2,LinkMirage

0.2
0

10

20

30

40

50

60

70

0.95
0.9
0.85
0.8
0.75
0.7
0.65
0.6
0

80

(a) Timestamp t

K=2,Mittal et al.
K=2,LinkMirage
1

2

3

4

5

6

7

8

(b) Timestamp t

Fig. 7. (a)(b) show the temporal anti-aggregation privacy for the Google+ dataset and the Facebook dataset, respectively. The anti-aggregation privacy decreases
as time evolves because more information is leaked with more perturbed graphs available. Leveraging selective perturbation, LinkMirage achieves much betteranti-aggregation privacy than the static baseline method.

design of such social network based systems, while preserving
the privacy of users’ social relationships. We restrict ouranalysis to low-latency anonymity systems that leverage social
links, such as the Pisces protocol [28].
Similar to the Tor protocol, users in Pisces rely on proxy
servers and onion routing for anonymous communication.
However, the relays involved in the onion routing path arechosen by performing a random walk on a trusted social
network topology. Recall that LinkMirage better preserves theevolution of temporal graphs in Fig. 3. We now show that thistranslates into improved anonymity over time, by performing
an analysis of the degradation of user anonymity over multiple
graph snapshots. For each graph snapshot, we consider a worst
case anonymity analysis as follows: if a user’s neighbor in thesocial topology is malicious, then over multiple communication rounds (within that graph instance) its anonymity will becompromised using state-of-the-art traffic analysis attacks [41].
Now, suppose that all of a user’s neighbors in the first graphinstance are honest. As the perturbed graph sequence evolves,
there is further potential for degradation of user anonymity
since in the subsequent instances, there is a chance of the user
connecting to a malicious neighbor. Suppose the probability
for a node to be malicious is f . Denote nt (v) as the distinct
neighbors of node v at time t. For a temporal graph sequence,
the number of the union neighbors ∪tk=0 nk (v) of v increases
with time, and the probability for v to be attacked under thetworst case is Ptattack (v) = 1 − (1 − f )|∪k=0 nk (v)| . Note that inpractice, the adversary’s prior information will be significantly
less than the worst-case adversary.
Fig. 8 depicts the degradation of the worst-case anonymity
with respect to the number of perturbed topologies. We cansee that the attack probability for our method is lower than thestatic approach with a factor up to 2. This is because over consecutive graph instances, the users’ social neighborhood has
higher similarity as compared to the static approach, reducing
potential for anonymity degradation. Therefore, LinkMirage
can provide better security for anonymous communication, andother social trust based applications.

Attack probability

10.9

k=5,Mittal et al.
k=5,LinkMirage
k=20,Mittal et al.
k=20,LinkMirage

0.8
0.7
0.6
0.5
0

1

2

3

4
5
Timestamp t

6

7

8

Fig. 8. The worst case probability of deanonymizing users’ communications(f = 0.1). Over time, LinkMirage provides better anonymity compared to thestatic approaches.

F. Summary for Privacy Analysis• LinkMirage provides rigorous privacy guarantees to defend
against adversaries who have prior information about theoriginal graphs, and the adversaries who aim to combine
multiple released graphs to infer more information.
• LinkMirage shows significant privacy advantages in antiinference privacy, indistinguishability and anti-aggregation
privacy, by outperforming previous methods by a factor up
to 10.
VI.

A PPLICATIONSApplications such as anonymous communication [11], [28],[29] and vertex anonymity mechanisms [25], [34], [45] can utilize LinkMirage to obtain the entire obfuscated social graphs.
Alternatively, each individual user can query LinkMirage forhis/her perturbed neighborhoods to set up distributed social relationship based applications such as SybilLimit [43]. Further,
the OSN providers can also leverage LinkMirage to perturb
the original social topologies only once and support multiple
privacy-preserving graph analytics, e.g., privately compute thepagerank/modularity of social networks.
A. Anonymous Communication [11], [28], [29]B. Vertex Anonymity [25], [34], [45]As a concrete application, we consider the problem ofanonymous communication [11], [28], [29]. Systems foranonymous communication aim to improve user’s privacy
by hiding the communication link between the user and theremote destination. Nagaraja et al. and others [11], [28], [29]have suggested that the security of anonymity systems can be
improved by leveraging users’ trusted social contacts.
We envision that our work can be a key enabler for thePrevious work for vertex anonymity [25], [34], [45] would
be defeated by de-anonymization techniques [20], [30], [32],[37]. LinkMirage can serve as a formal first step for vertex
anonymity, and even improve its defending capability against
de-anonymization attacks. We apply LinkMirage to anonymize
vertices, i.e. to publish a perturbed topology without labelingany vertex. In [20], Ji et al. modeled the anonymization as
10

100

1000

% False positive rate

80

Final attack edges

Original
k=5
k=20

90

70
60
50
40

800

Original
k=5
k=20

600

400

200

30
20
0

5

10

(a) Random walk length

15

0
0

20

200

400

600

800

1000

1200

(b) Attack edges

Fig. 9. (a) shows the false positive rate for Sybil defenses. We can see that the perturbed graphs have lower false positive rate than the original graph. Random
walk length is proportional to the number of Sybil identities that can be inserted in the system. (b) shows that the final attack edges are roughly the same forthe perturbed graphs and the original graphs.

a sampling process where the sampling probability p denotes
the probability of an edge in the original graph Go to exist in
the anonymized graph G0 . LinkMirage can also be applied forsuch model, where the perturbed graph G0 is sampled fromthe k-hop graph Gk (corresponding to Go ).
They also derived a theoretical bound of the sampling probability p for perfect de-anonymization, and found that a weakerbound is needed with a larger value of the sampling probability
p. Larger p implies that G0 is topologically more similar to G,
making it easier to enable a perfect de-anonymization. Whenconsidering social network evolution, the sampling probability
p can be estimated as |E(G00 , · · · , G0t )|/|E(Gk0 , · · · , Gkt )|,where E(G00 , · · · , G0t ) are the edges of the perturbed graphsequence, and E(Gk0 , · · · , Gkt ) are the edges of the k-hop
graph sequence. Compared with the static baseline approach,
LinkMirage selectively reuses information from previously
perturbed graphs, thus leading to smaller overall sampling
probability p, which makes it harder to perfectly de-anonymize
the graph sequence. For example, the average sampling probability p for the Google+ dataset (with k = 2) is 0.431 and
0.973 for LinkMirage and the static method respectively. For
the Facebook temporal dataset (with k = 3), the average
sampling probability p is 0.00012 and 0.00181 for LinkMirage
and the static method respectively. Therefore, LinkMirage ismore resilient against de-anonymization attacks even whenapplied to vertex anonymity, with up to 10x improvement.

TABLE III. Modularity of Perturbed Graph Topologies
LinkMirage LinkMirage Mittal et al. Mittal et al.
Google+ Original
Graph
k=2
k=5
k=2
k=5
Modularity 0.605
0.601
0.603
0.591
0.586
LinkMirage LinkMirage Mittal et al. Mittal et al.
Facebook Original
Graph
k=5
k = 20k=5
k = 20Modularity 0.488
0.479
0.487
0.476
0.415

improves Sybil resilience and provides the privacy of the social
relationships such that Sybil defense protocols continue to be
applicable (similar to static approaches whose Sybil-resilience
performance have been demonstrated in previous work).
D. Privacy-preserving Graph Analytics [31], [33]Next, we demonstrate that LinkMirage can also benefit
the OSN providers for privacy-preserving graph analytics.
Previous work in [12], [13] have demonstrated that the implementation of graph analytic algorithms would also result in
information leakage. To mitigate such privacy degradation, theOSN providers could add perturbations (noises) to the outputsof these graph analytics. However, if the OSN providers aim
to implement multiple graph analytics, the process for adding
perturbations to each output would be rather complicated.
Instead, the OSN providers can first obtain the perturbed graphby leveraging LinkMirage and then set up these graph analytics
in a privacy-preserving manner.
Here, we first consider the pagerank [33] as an effective
graph metric. For the Facebook dataset, we have the average
differences between the perturbed pagerank score and theoriginal pagerank score as 0.0016 and 0.0018 for k = 5
and k = 20 respectively in LinkMirage. In comparison,
the average differences are 0.0019 and 0.0087 for k = 5
and k = 20 in the approach of Mittal et al. LinkMirage
preserves the pagerank score of the original graph with up
to 4x improvement over previous methods. Next, we show
the modularity [31] (computed by the timestamp t = 3 in
the Google+ dataset and the Facebook dataset, respectively)
in Table III. We can see that LinkMirage preserves both thepagerank score and the modularity of the original graph, while
the method of Mittal et al. degrades such graph analytics
especially for larger perturbation parameter k (recall the visual
intuition of LinkMirage in Fig. 3).

C. Sybil Defenses [43]Next, we consider Sybil defenses systems which leverage
the published social topologies to detect fake accounts in thesocial networks. Here, we analyze how the use of a perturbed
graph changes the Sybil detection performance of SybilLimit[43], which is a representative Sybil defense system. Each user
can query LinkMirage for his/her perturbed friends to set up
the implementation of SybilLimit. Fig. 9(a) depicts the false
positives (honest users misclassified as Sybils) with respect tothe random walk length in the Sybillimit protocol. Fig. 9(b)shows the final attack edges with respect to the attack edges
in the original topology. We can see that the false positive rate
is much lower for the perturbed graphs than for the originalgraph, while the number of the attack edges stay roughly
the same for the original graph and the perturbed graphs.
The number of Sybil identities that an adversary can insert
is given by S = g 0 · w0 (g 0 is the number of attack edges
and w0 is the random walk parameter in the protocol). Since
g 0 stays almost invariant and the random walk parameter w0(for any desired false positive rate) is reduced, LinkMirage

E. Summary for Applications of LinkMirage• LinkMirage preserves the privacy of users’ social contacts
while enabling the design of social relationships based
11

properties of social networks. In fact, a lot of social network
based security applications such as Sybil defenses [43] andanonymity systems [28] directly perform random walks intheir protocols. The parameter l is application specific; forapplications that require access to fine grained local structures, such as recommendation systems [2], the value of lshould be small. For other applications that utilize coarse andmacro structure of the social graphs, such as Sybil defense
mechanisms, l can be set to a larger value (typically around10 in [43]). Therefore, this utility metric can quantify theutility performance of LinkMirage for various applications ina general manner.
Note that LinkMirage is not limited to only preserving thecommunity structure of the original graphs. We evaluate two
representative graph theoretic metrics clustering coefficient andassortativity coefficient [14] as listed in Table IV. We cansee that LinkMirage well preserves such fine-grained structuralproperties for smaller perturbation parameter k. Therefore, theextent to which the utility properties are preserved depends on
the perturbation parameter k.

TABLE IV. Graph Metrics of the Original and the Perturbed
Graphs for the Google+ Dataset.
Original Graph
LinkMirage k = 2
LinkMirage k = 5
LinkMirage k = 10
LinkMirage k = 20

Clustering Coefficient
0.26120.22630.18290.08640.0136

Assortativity Coefficient-0.0152-0.0185-0.0176-0.0092-0.0063

applications. Compared to previous methods, LinkMirage
results in significantly lower attack probabilities (with afactor up to 2) when applied to anonymous communications
and higher resilience to de-anonymization attacks (with afactor up to 10) when applied to vertex anonymity systems.
• LinkMirage even surprisingly improves the Sybil detection
performance when applied to the distributed SybilLimit
systems.
• LinkMirage preserves the utility performance for multiple
graph analytics applications, such as pagerank score andmodularity with up to 4x improvement.
VII.

B. Relationships with Other Graph Structural Properties

U TILITY A NALYSIS

The mixing time τ (Gt ) measures the time required for
the Markov chain to converge to its stationary distribution, andis defined as τ (Gt ) = minr maxv (r |Ptr (v) − πt |TV < ).
Based on the Perron-Frobenius theory, we denote the eigenvalues of Pt as 1 = µ1 (Gt ) ≥ µ2 (Gt ) ≥ · · · µ|Vt | (Gt ) ≥ −1.
The convergence rate of the Markov chain to πt is determined by the second largest eigenvalue
modulus (SLEM) asµ(Gt ) = max µ2 (Gt ), −µ|Vt | (Gt ) .
Since our utility distance is defined by using the transition
probability matrix Pt , this metric can be proved to be closely
related to structural properties of the graphs, as shown in
Theorem 5 and Theorem 6.

Following the application analysis in Section VI, we aim
to develop a general metric to characterize the utility ofthe perturbed graph topologies. Furthermore, we theoreticallyanalyze the lower bound on utility for LinkMirage, uncoverconnections between our utility metric and structural propertiesof the graph sequence, and experimentally analyze our metricusing the real-world Google+ and Facebook datasets.
A. Metrics
We aim to formally quantify the utility provided by LinkMirage to encompass a broader range of applications. One
intuitive global utility metric is the degree of vertices. It isinteresting to find that the expected degree of each node in
the perturbed graph is the same as the original degree and wedefer the proof to Appendix to improve readability.

Theorem 5: Let us denote the utility distance between
the perturbed graph G0t and the original graph Gt byUD(Gt , G0t , l), then we have τG0t (UD (Gt , G0t , τGt ()) − ) ≥
τGt ().

Theorem 4: The expected degree of each node after perturbation by LinkMirage is the same as in the original graph:∀v ∈ Vt , E(deg0 (v)) = deg(v), where deg0 (v) denotes thedegree of vertex v in G0t .

Theorem 6: Let us denote the second largest eigenvalue
modulus (SLEM) of transition probability matrix Pt ofgraph Gt as µGt . We can bound the SLEM of a perturbed
graph G0t using the mixing time of the original graph, andthe utility distance between the graphs as µG0t ≥ 1 −To understand the utility in a fine-grained level, we further
define our utility metric as

log n+log UD(G ,G0 1,τt

τGt ()Definition 4: The Utility Distance (UD) of a perturbed
graph sequence G00 , · · · , G0T with respect to the original graphsequence G0 , · · · , GT , and an application parameter l is defined as
UD(G0 , · · · GT , G00 , · · · G0T , l)T
1 XX 1=
kP l (v) − (Pt0 )l (v)kT V
T + 1 t=0
|Vt | tt

Gt ())−

.

C. Upper Bound of Utility Distance
LinkMirage aims to limit the degradation of link privacy
over time. Usually, mechanisms that preserve privacy tradeoff application utility. In the following, we will theoreticallyderive an upper bound on the utility distance for our algorithm.
This corresponds to a lower bound on utility that LinkMirage
is guaranteed to provide.
Theorem 7: The utility distance of LinkMirage is upperbounded by 2l times the sum of the utility distance of each
community  and the ratio cut δt for each Gt , i.e.

(5)

v∈Vt

Our definition for utility distance in Eq. 5 is intuitively
reasonable for a broad class of real-world applications, andcaptures the behavioral differences of l-hop random walks
between the original graphs and the perturbed graphs. We
note that random walks are closely linked to the structural

UD(G0 , · · · GT , G00 , · · · G0T , l) ≤

12

T
1 X
2l( + δt ) (6)T + 1 t=0

1

1

k=2
k=5

k=5
k=20

0.8

Utility distanceUtility Distance

0.8
0.6
0.4

0.6
0.4
0.2

0.2
0
0

5

10

15

0

20

4

6

8

10

12

14

16

18

20

(b) Application level parameter l(a) Application level parameter l

Fig. 10. (a), (b) show the utility distances using the Google+ dataset and the Facebook dataset, respectively. Larger perturbation parameter k results in larger
utility distance. Larger application parameter l decreases the distance, which shows the effectiveness of LinkMirage in preserving global community structures.

where δt denotes the number of inter-community links overthe number of vertices, and each community Ck(t) within Gt
0satisfies kCk(t) − Ck(t)kT V ≤ . We defer the proofs to the
Appendix to improve readability.
Note that an upper bound on utility distance corresponds
to a lower bound on utility of our algorithm. While better
privacy usually requires adding more noise to the original
sequence to obtain the perturbed sequence, thus we can seethat LinkMirage is guaranteed to provide a minimum level ofutility performance.
In the derivation process, we do not take specific evolutionary pattern such as the overlapped ratio into consideration,
therefore our theoretical upper bound is rather loose. Next,
we will show that in practice, LinkMirage achieves smaller
utility distance (higher utility) than the baseline approach of
independent static perturbations.

serves as the foundation for our algorithm. Their method
deletes all edges in the original graph, and replaces each edge
with a fake edge that is sampled based on the structural properties of the graph. In particular, random walks are performedon the original graph to sample fake edges. As compared to themethods of Hay et al. [16] and Mittal et al. [27], LinkMirage
provides up to 3x privacy improvement for static social graphs
and up to 10x privacy improvement for dynamic social graphs.
Another line of research aims to preserve link privacy [15][44] by aggregating the vertices and edges into super vertices.
Therefore, the privacy of links within each super vertex isnaturally protected. However, such approaches do not permit
fine grained utilization of graph properties, making it difficult
to be applied to applications such as social network based
anonymous communication and Sybil defenses.
Privacy with unlabeled vertices While the focus of our paper
is on preserving link privacy in context of labeled vertices,an orthogonal line of research aims to provide privacy inthe context of unlabeled vertices (vertex privacy) [4], [25],[34]. Liu et al. [25] proposed k-anonymity to anonymize
unlabeled vertices by placing at least k vertices at an equivalentlevel. Differential privacy provides a theoretical frameworkfor perturbing aggregate information, and Sala et al. [34]leveraged differential privacy to privately publish social graphswith unlabeled vertices. We note that LinkMirage can also
provide a foundation for preserving vertex privacy as stated in
Section VI-B. Shokri et al. [35] addresses the privacy-utility
trade-off by using game theory, which can be generalized
to consider the temporal effects by updating the prior after
each iteration. In [39], they take the correlation over time into
account on the utility-privacy game designed in [36].
We further consider anonymity in temporal graphs with
unlabeled vertices. The time series data should be seriously
considered, since the adversaries can combine multiple published graph to launch enhanced attacks for inferring more
information. [5], [10], [38] explored privacy degradation invertex privacy schemes due to the release of multiple graphsnapshots. These observations motivate our work, even though
we focus on labeled vertices.
De-anonymization In recent years, the security community
has proposed a number of sophisticated attacks for deanonymizing social graphs [20], [30], [32], [37]. While mostof these attacks are not applicable to link privacy mechanisms (their focus is on vertex privacy), they illustrate theimportance of considering adversaries with prior information
about the social graph5 . We perform a rigorous privacy anal-

D. Utility Experiments Analysis
Fig. 10(a)(b) depict the utility distance for the Google+ and
the Facebook graph sequences, for varying perturbation degreek and the application level parameter l. We can also see thatas k increases, the distance metric increases. This is natural
since additional noise increase the distance between probability
distributions computed from the original and the perturbed
graph series. As the application parameter l increases, the distance metric decreases. This illustrates that LinkMirage is moresuited for security applications that rely on macro structures,as opposed to applications that require exact information about
one or two hop neighborhoods. Furthermore, our experimental
results in Table III also demonstrate the utility advantage of
our LinkMirage over the approach of Mittal et al. [27] in realworld applications.
VIII.

R ELATED W ORK

Privacy with labeled vertices An important thread of researchaims to preserve link privacy between labeled vertices by
obfuscating the edges, i.e., by adding /deleting edges [16],[27], [42]. These methods aim to randomize the structure of
the social graph, while differing in the manner of adding noise.
Hay et al. [16] perturb the graph by applying a sequence ofr edge deletions and r edge insertions. The deleted edges
are uniformly selected from the existing edges in the originalgraph while the added edges are uniformly selected from thenon-existing edges. However, neither the edge deletions noredge insertions take any structural properties of the graph into
consideration. Ying and Wu [42] proposed a new perturbation
method for preserving spectral properties, without analyzing
its privacy performance.
Mittal et al. proposed a perturbation method in [27], which

5 Burattin et al [6] exploited inadvertent information leaks via Facebook’s
graph API to de-anonymize social links; Facebook’s new graph API (v2.0)
features stringent privacy controls as a countermeasure.

13

ysis of LinkMirage (Section V) by considering a worst-case(strongest) adversary that knows the entire social graph except
one link, and show that even such an adversary is limited in
its inference capability.
IX. D ISCUSSION
Privacy Utility Tradeoffs: LinkMirage mediates privacypreserving access to users’ social relationships. In our privacy
analysis, we consider the worst-case adversary who knows
the entire social link information except one link, whichconservatively demonstrates the superiority of our algorithm
over the state-of-the-art approaches. LinkMirage benefits many
applications that depend on graph-theoretic properties of thesocial graph (as opposed to the exact set of edges). This also
includes recommendation systems and E-commerce applications.
Broad Applicability: While our theoretical analysis of
LinkMirage relies on undirected links, the obfuscation algorithm itself can be generally applied to directed social
networks. Furthermore, our underlying techniques have broad
applicability to domains beyond social networks, including
communication networks and web graphs.
X. C ONCLUSION
LinkMirage effectively mediates privacy-preserving accessto users’ social relationships, since 1) LinkMirage preserves key structural properties in the social topology whileanonymizing intra-community and inter-community links; 2)
LinkMirage provides rigorous guarantees for the anti-inference
privacy, indistinguishability and anti-aggregation privacy, inorder to defend against sophisticated threat models for both
static and temporal graph topologies; 3) LinkMirage significantly outperforms baseline static techniques in terms of both
link privacy and utility, which have been verified both theoretically and experimentally using real-world Facebook dataset(with 870K links) and the large-scale Google+ dataset (with940M links). LinkMirage enables the deployment of real-worldsocial relationship based applications such as graph analytic,
anonymity systems, and Sybil defenses while preserving theprivacy of users’ social relationships.
XI. ACKNOWLEDGEMENT
We would like to thank the anonymous reviewers at NDSS
2016 for helpful feedback, and we are especially grateful to
Reza Shokri for his guidance as our shepherd. This work was
supported in part by NSF awards number CNS-1409415 andCNS-1423139.

[7]

T. M. Cover and J. A. Thomas, Elements of information theory. John
Wiley & Sons, 2012.

[8]

G. Danezis and P. Mittal, “Sybilinfer: Detecting sybil nodes using social
networks.” in NDSS, 2009.

[9]

R. Dey, Z. Jelveh, and K. Ross, “Facebook users have become much
more private: a large scale study,” in IEEE SESOC, 2012.

[10]

X. Ding, L. Zhang, Z. Wan, and M. Gu, “De-anonymizing dynamic
social networks,” in GLOBECOM, 2011.

[11]

R. Dingledine, N. Mathewson, and P. Syverson, “Tor: The secondgeneration onion router,” in USENIX Security, 2004.

[12]

C. Dwork, “Differential privacy,” in Automata, languages and programming. Springer, 2006.

[13]

C. Dwork and J. Lei, “Differential privacy and robust statistics,” in
STOC, 2009.

[14]

N. Z. Gong, W. Xu, L. Huang, P. Mittal, E. Stefanov, V. Sekar,
and D. Song, “Evolution of social-attribute networks: measurements,
modeling, and implications using google+,” in IMC, 2012.

[15]

M. Hay, G. Miklau, D. Jensen, D. Towsley, and P. Weis, “Resisting
structural re-identification in anonymized social networks,” Proceedingsof the VLDB Endowment, 2008.

[16]

M. Hay, G. Miklau, D. Jensen, P. Weis, and S. Srivastava, “Anonymizing social networks,” Technical Report, University of Massachusetts,
Amherst, 2007.

[17]

H. Hodson, “Google software lets you get online via your friends,” New
Scientist, 2013.

[18]

R. A. Horn and C. R. Johnson, Matrix analysis. Cambridge university
press, 2012.

[19]

S. Ji, W. Li, P. Mittal, X. Hu, and R. Beyah, “Secgraph: A uniform
and open-source evaluation system for graph data anonymization andde-anonymization,” in Usenix Security, 2013.

[20]

S. Ji, W. Li, M. Srivatsa, and R. Beyah, “Structural data deanonymization: Quantification, practice, and implications,” in CCS,
2014.

[21]

Y. Kim and J. Srivastava, “Impact of social influence in e-commerce
decision making,” in Proceedings of the ninth international conference
on Electronic commerce, 2007.

[22]

A. Kyrola, G. E. Blelloch, and C. Guestrin, “Graphchi: Large-scalegraph computation on just a pc.” in OSDI, 2012.

[23]

N. Li, W. Qardaji, D. Su, Y. Wu, and W. Yang, “Membership privacy:
a unifying framework for privacy definitions,” in CCS, 2013.

[24]

D. Liben-Nowell and J. Kleinberg, “The link-prediction problem forsocial networks,” Journal of the American society for information
science and technology, 2007.

[25]

K. Liu and E. Terzi, “Towards identity anonymization on graphs,” in
SIGMOD, 2008.

[26]

A. Mislove, A. Post, P. Druschel, and P. K. Gummadi, “Ostra: Leveraging trust to thwart unwanted communication.” in NSDI, 2008.

[27]

P. Mittal, C. Papamanthou, and D. Song, “Preserving link privacy insocial network based systems,” in NDSS, 2013.

[28]

P. Mittal, M. Wright, and N. Borisov, “Pisces: Anonymous communication using social networks,” in NDSS, 2013.

[29]

S. Nagaraja, “Anonymity in the wild: mixes on unstructured networks,”
in PETS, 2007.

[30]

A. Narayanan and V. Shmatikov, De-anonymizing social networks.
IEEE S&P, 2009.

[31]

M. E. Newman, “Modularity and community structure in networks,”
Proceedings of the National Academy of Sciences, 2006.

[32]

S. Nilizadeh, A. Kapadia, and Y.-Y. Ahn, “Community-enhanced deanonymization of online social networks,” in CCS, 2014.

[33]

L. Page, S. Brin, R. Motwani, and T. Winograd, “The pagerank citation
ranking: Bringing order to the web.” 1999.

[34]

A. Sala, X. Zhao, C. Wilson, H. Zheng, and B. Y. Zhao, “Sharing graphs
using differentially private graph models,” in IMC, 2011.

[35]

R. Shokri, “Privacy games: Optimal user-centric data obfuscation,” inPETS, 2015.

R EFERENCES
[1]

[2]

[3]

[4]
[5]
[6]

L. J. Almeida and A. de Andrade Lopes, “An ultra-fast modularity-basedgraph clustering algorithm,” in Proceedings 14th Portuguese Conferenceon Artificial Intelligence (EPIA), 2009.
R. Andersen, C. Borgs, J. Chayes, U. Feige, A. Flaxman, A. Kalai,
V. Mirrokni, and M. Tennenholtz, “Trust-based recommendation systems: an axiomatic approach,” in WWW, 2008.
T. Aynaud, E. Fleury, J.-L. Guillaume, and Q. Wang, “Communities in
evolving networks: Definitions, detection, and analysis techniques,” inDynamics On and Of Complex Networks, 2013.
F. Beato, M. Conti, and B. Preneel, “Friend in the middle (fim): Tacklingde-anonymization in social networks,” in PERCOM, 2013.
S. Bhagat, G. Cormode, B. Krishnamurthy, and D. Srivastava, “Privacy
in dynamic social networks,” in WWW, 2010.
A. Burattin, G. Cascavilla, and M. Conti, “Socialspy: Browsing (supposedly) hidden information in online social networks,” arXiv preprint,
2014.

14

[36]

[37]
[38]
[39]

[40]
[41]

[42]
[43]
[44]
[45]

derivation process, we partition the proof into two stages. In the first stage,
we derive the UD upper bound for the intermediate perturbation method. In0the second stage, we derive the relationship between G0,it and Gt . Resultsfrom the two stages can be combined to find the upper bound for the utility
distance of LinkMirage. Denoting the communities as C1 , C2 , ·, CKt andthe inter-community subgraphs as C12 , C13 , · · · , we have

R. Shokri, G. Theodorakopoulos, C. Troncoso, J.-P. Hubaux, and J.Y. Le Boudec, “Protecting location privacy: optimal strategy against
localization attacks,” in CCS, 2012.
M. Srivatsa and M. Hicks, “Deanonymizing mobility traces: Usingsocial network as a side-channel,” in CCS, 2012.
C.-H. Tai, P.-J. Tseng, P. S. Yu, and M.-S. Chen, “Identities anonymization in dynamic social networks,” in ICDE, 2011.
G. Theodorakopoulos, R. Shokri, C. Troncoso, J.-P. Hubaux, and L. B.
Jean-Yves, “Prolonging the hide-and-seek game: Optimal trajectoryprivacy for location-based services,” in WPES, 2014.
B. Viswanath, A. Mislove, M. Cha, and K. P. Gummadi, “On theevolution of user interaction in facebook,” in WOSN, 2009.
M. Wright, M. Adler, B. N. Levine, and C. Shields, Defending Anonymous Communications Against Passive Logging Attacks. IEEE S&P,
2003.
X. Ying and X. Wu, “Randomizing social networks: a spectrum preserving approach,” in SDM, 2008.
H. Yu, P. B. Gibbons, M. Kaminsky, and F. Xiao, Sybillimit: A nearoptimal social network defense against sybil attacks. IEEE S&P, 2008.
E. Zheleva and L. Getoor, “Preserving the privacy of sensitive relationships in graph data,” in PinKDD, 2008.
B. Zhou, J. Pei, and W. Luk, “A brief survey on anonymization
techniques for privacy preserving publishing of social network data,”
ACM SIGKDD Explorations Newsletter, 2008.

XII.

kPt − Pt 0,i kTV00
Pt(1,1) − Pt(1,1)...
Pt(1,Kt ) − Pt(1,Kt)
00Pt(2,1) − Pt(2,1)...
Pt(2,Kt ) − Pt(2,K
t)
=
..
..
..
.
.
.
0
0
Pt(Kt ,1) − Pt(K. . . Pt(Kt ,Kt ) − Pt(Kt ,1)t ,Kt )X
Kt
1
0
|Vt (k)|kPt(k,k) − Pt(k,k) kTV
=
k=1
|Vt |
1 XKt
0
+
|Et (k, j)|kPt(k,j) − Pt(k,j)
kTV
k,j=1,k6=j|Vt |≤  + δt

(7)

Here,
PKt δt is the ratio cut of the graph [1], and δt = |Et−in |/|Vt | =k,j=1,k6=j |Et (k, j)|/|Vt |. For arbitrary matrix P and Q, we havekP l − Ql kTV ≤ lkP − QkTV . Combining the above results, we have0,iUD(Gt , G0,it , l) ≤ lkPt − Pt kTV ≤ l ( + δt ). Then, we generalize
the utility analysis of intermediate perturbation to our dynamic perturbation.
Assume that there are Ktc out of Kt clusters that are considered as changed,
which would be perturbed independently, and Ktu out of Kt clusters are
considered as unchanged, i.e., their perturbation would follow the perturbationmanner in G0t−1 . To simplify derivation, we use Pt(k) instead of Pt(k,k) torepresent the TPM of the k-th community. Then, we have

A PPENDIX

A. Proof of the Upper Bound of Anti-aggregation Privacy
k−1
1 P|Vt |−kPtk − Pt0 kTV = kPtk − P̂tk kTV ≤ 2|V
v=1 kPt (v)Pt
t|
P
|V
|
k−1
k−1
1
t
k
P̂
(v)P
−
P̂
(v)
P̂
k
=
P̂t (v)Ptk−1 k1 + 2|V
t
t
1
t
t
v=1
|

UD(Gt , G0t , 1) = kPt − Pt0 kTV
PKtu
PKtc
0
0
j=1 kPt(j) − Pt(j) kTV
k=1 kPt(k) − Pt(k) kTV +
+ δt
≤
|Kt |
 c
Ktu
Kt
X
1 X
0
≤
kPt(j) − P(t−1)(j) kTV
kPt(k) − Pt(k)kTV +|Kt | k=1
j=1

0
0
0
+kP(t−1)(j) − P(t−1)(j)kTV + kP(t−1)(j)− Pt(j)
kTV
+ δt
PKt
0
|Ktu |0
k=1 kPt(k) − Pt (k)kTV
=
+
+ δt
|Kt |
|Kt |

t

kPt − P̂t kTV + kPtk−1 − P̂tk−1 kTV ≤ kkPt − P̂t kTV .
B. Relationships with Differential Privacy When considering
differential privacy for a time series of graph sequence {Gi }ti=0 ,e i (Lt )}t , Lt = 1), f (D0 ) =we have f (D) = P ({G0i }ti=0 |{Gi=0e i (Lt )}t , Lt
P ({G0i }ti=0 |{G=0). For a good privacy
i=0
e i (Lt )}t , Lt
performance, we need P ({G0i }ti=0 |{G
=
1)
≈
i=0
0
t
t
e
P ({Gi }i=0 |{Gi (Lt )}i=0 , Lt=
0).
Since the probability ofe i (Lt )}te i (Lt )}t ){G0i }ti=0 given {Gas P ({G0i }ti=0 |{G
=
i=0
i=0
0
t
t
e
e i (Lt )}t ) +P ({Gi }i=0 |{Gi (Lt )}i=0 , Lt = 1)P (Lt = 1|{Gi=0e i (Lt )}t , Lte i (Lt )}t ,P ({G0i }ti=0 |{G=0)P (Lt
=
0|{G
i=0
i=0
it is easy to see that if the condition for a good privacy
0tte
performance holds, we have P (Lt |{Gi }i=0 , {Gi (Lt )}i=0 )=e i (Lt )}t ,Lt )×P (Lt |{G
e i (Lt )}t )P ({G0i }ti=0 |{Gi=0i=0e i (Lt )}t ),≈ P (Lt |{G
e i (Lt )}t )P ({G0i }ti=0 |{G
i=0

TV

(8)

≤ UD(Gt , G0,it , 1) +  + δt
where 0 denotes the threshold to classify a community as changed
or unchanged. The last inequality comes from the fact that 0 ≤ .
Then, we can prove UD (Gt , G0t , l) = kPtl − (Pt0 )l kTV≤
lkPt − Pt0 kTV ≤ lkPt − Pt0,i kTV + l( + δt ) = 2l ( + δt ) and1 PT
UD(G0 , · · · GT , G00 , · · · G0T , l) ≤ T +1
t=0 2l( + δt ).

i=0

which is the same as in Definition 1 and means that the posterior probability
is similar to the prior probability, i.e., the adversary is bounded in theinformation it can learn from the perturbed graphs.

E. Proof for Relating Utility Distance with Structural Metrics
From the definition of total variation distance, we have kPvr (G0t ) − πkT V +kPvr (Gt ) − πkT V ≥ kPvr (G0t ) − Pvt (G)kT V . Taking the maximum overall vertices, we have max kPvr (G0t ) + πkT V + max kPvr (Gt ) − πkT V ≥max kPvr (G0t ) − Pvt (G)kT V . Therefore, for t≥
τG (),
max kPvr (G0t ) − πkT V ≥ max kPvr (G0t ) − Pvt (G)kT V + max kPvr (Gt ) −C. Proof of Theorem 4: Expectation of Perturbed Degree According to
Theorem 3 in [27], we have E(deg0com (v)) = deg(v), where deg0com (v)denotes the degree of v after perturbation within community. Then we
consider the random perturbation for inter-community subgraphs. Sincedeg(va (i)) deg(vb (j))|va |the probability for an edge to be chosen is,|Eab |(|va |+|vb |)the expected degree after inter-community perturbation satisfiesP
deg(va (i)) deg(vb (j))(|va |+|vb |)E(deg0inter (va (i))) = j|Eab |(|va |+|vb |)= deg(va (i)). Combining with the expectations under static scenario, we
have E(deg0 (v)) = deg(v).

P|Vt |

kP r (G0 )−P t (G)k

−πk

TV
TV
− = UD(Gt , G0t , τG ())−.
πkT V ≥ v=1 v t |V v|
tThen, we have τG0 (UD (Gt , G0t , τGt ()) − ) ≥ τGt (). It istknown that the second largest eigenvalue modulus is related to the≤mixing time of the graph as τG0 ()tlog n+log 1

.
1−µG0

From thistrelationship, we can bound the SLEM in terms of the mixing time as

D. Proof of the Upper Bound for the Utility Distance We first
introduce some notations and concepts. We consider two perturbation
methods in the derivation process below. The first method is our dynamic
perturbation method, which takes the graph evolution into consideration.
The second method is the intermediate method, where we only implement
dynamic clustering without selective perturbation. That is to say, wecluster Gt , then perturb each community by the static method and eachinter-community subgraphs by randomly connecting the marginal nodes,
independently. We denote the perturbed graphs corresponding to the dynamic,
the intermediate method by G0t , G0,i
respectively. Similarly, we denotet
the perturbed TPM for the two approaches by Pt0 , Pt0,i . To simplify the1−

log n+log ( 1
)

τG0
t

≤ µG0 . Replacing  with UD(Gt , G0t , τGt ()) − ,t

1
UD(Gt ,G0t ,τG ())−t0
τG0 (UD(Gt ,Gt ,τGt ()))−
tlog n+log

we have 1 −≤ µG0 . Finally, we leveragetτG0 (UD(Gt , G0t , τGt () − )) ≥ τGt () in the above equation, to obtaint
1
log n+log0µG0 ≥ 1 −t

15

UD(Gt ,Gt ,τG ())−t
τGt ().