IEEE INFOCOM 2016 - The 35th Annual IEEE International Conference on Computer Communications

On the Relative De-anonymizability of Graph Data:
Quantification and Evaluation†

Shouling Ji† , Weiqing Li† , Shukun Yang† , Prateek Mittal‡ , and Raheem Beyah†
School of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta, GA 30332-0765, USA‡
Department of Electrical Engineering, Princeton University, Princeton, NJ 08544, USA
Email: {sji, wli64, syang87}@gatech.edu, pmittal@princeton.edu, rbeyah@ece.gatech.edu

Abstract—In this paper, we propose a structural importanceaware approach to quantify the vulnerability/de-anonymizabilityof graph data to structure-based De-Anonymization (DA) attacks[1][2][3][4]. Specifically, we quantify both the seed-based and theseed-free Relative De-anonymizability (RD) of graph data for both
perfect DA (successfully de-anonymizing all the target users)
and partial DA (where some DA error is tolerated) under ageneral data model. In our relative quantification, instead oftreating all the users in graph data as structurally equivalent,
we adaptively quantify their RD in terms of their structural
importance. Leveraging 15 real world graph datasets, we validate
the accuracy of our relative quantifications and compare themwith state-of-the-art seed-based and seed-free quantification techniques. The results demonstrate that our structural importanceaware relative quantifications are more sound and precise whenmeasuring graph data’s real vulnerability/de-anonymizability.

I. I NTRODUCTION
Graph data (e.g., social network data, contact data, healthcare data) are critical for academic research, government applications, commercial collaborations, healthcare applications,and other data mining tasks [1][5][6][7]. Therefore, graphdata are frequently shared with researchers, government agencies, commercial parters, and other individuals/organizations[1][5][6][7]. One of the most notable characteristics of graphdata is that the data items are structurally correlated with eachother in addition to the semantic information they carried[1][5][6][7]. For instance, a user of a social network iscorrelated with other users in the network in addition to the
profile information associated with him/her. On one hand,the correlations carried by graph data make the data usefulfor comprehensive analysis and meaningful applications (e.g.,commercial and healthcare data mining and analysis tasks [1]).
On the other hand, these correlations allow graph data to suffer
security and privacy threats since adversaries can leveragethem to infer private information about the users/systems
who generated the graph data. As shown by recent research,
anonymized graph data can be successfully de-anonymized inlarge-scale by structure-based De-Anonymization (DA) attacks[1][5][6][7].
To understand “the underlying reason for the success ofexisting structure-based DA attacks”, recently, the concept ofgraph data de-anonymizability quantification has garnered significant research [5][8][9][10][11], where researchers study thefollowing: based on graph data’s structural information, whygraph data can be de-anonymized, what are the DA conditions,

978-1-4673-9953-1/16/$31.00 ©2016 IEEEand how many users are de-anonymizable, i.e., graph data deanonymizability quantification can quantitatively examine howvulnerable/de-anonymizable any (anonymized) graph dataset
is given its structure. Therefore, graph data de-anonymizability
quantification techniques can be employed to examine the theoretically achievable vulnerability of both raw and anonymized
graph data, and can thus evaluate the effectiveness of ananonymization scheme. Furthermore, the quantification results
can serve as auxiliary information that is useful for future
anonymization technique design and DA attack evaluation.
However, existing de-anonymizability quantifications[5][8][9][10][11] are limited due to some of the following
reasons. First, most existing quantification techniques areeither fully based on seed information, e.g., [8][10][11], or
do not consider seed information at all, e.g., [5][9], which
is an incomplete approach to graph data de-anonymizability
analysis. Second, most existing quantification techniques are
based on an impractical data model (e.g., the Erdös-Rényi(ER) model) and/or make impractical assumptions (e.g.,dense seeds are available). Finally, all the existing techniques
do not take into account the structural/topological importanceof users in their quantifications. In practice, different users
may have very different structural importance, e.g., the users
with the maximum and minimum degrees are structurally
different [2][12]. Therefore, existing quantification results
are incomplete with regards to quantifying graph data’s
actual/precise structure-based de-anonymizability, i.e., they
are inaccurate in quantifying graph data’s actual vulnerability
to structure-based DA attacks (we summarize existing deanonymizability quantification techniques and discuss theirlimitations in detail in Sections II).
Contributions. To address the limitations of existing techniques, we study the structural importance-aware Relative
De-anonymizability (RD) of graph data in this paper. Insteadof treating all the users as equivalent, we quantify the deanonymizability of anonymized graph data adaptively andaccurately by taking into account users’ structural differences.
Specifically, our contributions are summarized as follows.
1) We introduce the concept of structural importanceaware RD of graph data. Specifically, we formally define
𝜃-RD and (𝜃, 𝜖)-RD of graph data, where 𝜃 indicates thetarget DA users according to their structural importanceand 𝜖 characterizes the tolerated DA error by a DA
scheme.

2) Under a general data model, we quantify the seed-based
RD of graph data for both perfect DA (de-anonymizing
all the target users) and partial DA (where some DA error is tolerated). Our seed-based quantification provides
the most accurate theoretical foundation for the successof existing seed-based DA attacks (e.g.,[1][2][3]).
3) Under a general data model, we also quantify the seedfree RD of graph data for both perfect DA and partial
DA. Our seed-free quantification provides the most accurate theoretical foundation for the success of existing
seed-free DA attacks (e.g., [4][5]).
4) Leveraging 15 real world graph datasets, we conduct
a large-scale evaluation of our RD quantification techniques. We also evaluate the performance our quantifications against that of state-of-the-art quantification techniques. The evaluation results demonstrate that our structural importance-aware RD quantification techniques are
more sound and accurate when measuring graph data’s
real vulnerability/de-anonymizability.
The reminder of this paper is as follows. In Section II, wesummarize the related work. The system model and preliminaries are given in Section III. We quantify seed-based andseed-free RD of graph data in Sections IV and V, respectively.
The large-scale evaluation is conducted in Section VI. We
conclude this paper in Section VII.
II. R ELATED W ORK
A. Graph Data DA
In [3], Backstrom et al. proposed both active and passive
DA attacks to graph data based on subgraph pattern matching.
Later, Narayanan and Shmatikov proposed the first scalable
and robust two-phase DA attack in [1], where the first phaseis used for seed identification and the second phase is for
DA propagation. In addition, Narayanan et al. studied how to
perform link DA in [13] leveraging node/user DA. In [14],Nilizadeh et al. extended the attack in [1] and presented acommunity-enhanced DA attack. In [6], Srivatsa and Hicks presented three two-phase attacks similar to [1] to de-anonymize
contact graphs (constructed from mobility traces). In [2], Ji
et al. proposed another seed-based two-phase DA framework.
There are also seed-free DA attacks, e.g., in [5], a seed-free
optimization-based DA attack is designed. In [7], Ji et al.
developed SecGraph, a uniform and open-source evaluation
system for graph anonymization and de-anonymization.
B. De-anonymizability Quantification
1) Seed-based Quantification: In [10], Yartseva and Grossglauser quantified the de-anonymizability of graph data by
analyzing a percolation-based graph matching algorithm under
the Erdös-Rényi (ER) random graph model 𝐺(𝑛, 𝑝) (a randomgraph consists of 𝑛 nodes/users, and an edge exists between
any pair of nodes with probability 𝑝). However, it is seldom
to see that any real world graph data following the ER model(if not possible) [5][12], the quantification under the ER
model is only mathematically meaningful but not practical.
Nevertheless, it can shed light on more practical quantification.

Another limitation of [10] is that it leverages seed-associatedstructural information for de-anonymizability quantification. In
fact, as shown in [9][5], graph data is de-anonymizable based
solely on data’s structural information, i.e., without seeds.
Following the same direction, Korula and Lattanzi conducted another seed-based de-anonymizability quantificationof graph data under both the ER model and the Preferential
Attachment (PA) model [11]. However, the quantification in[11] is valid under a strong assumption of existing dense
seeds (Θ(𝜄 ⋅ 𝑛) available seeds, 𝜄 ∈ (0, 1] is a constant),
which is not true for real world DA attacks. Recently, Ji etal. also quantified the seed-based de-anonymizability of social
networks [8] under the ER model and a statistical model.
2) Seed-free Quantification: In [9], Pedarsani and Grossglauser quantified the de-anonymizability of graph data under
the ER model. Again, the quantification is under the mathematical ER model, which cannot be applied to real worldgraph data [5][12]. Ji et al. improved the quantification in [9].
Similar to [9], the authors did not employ seeds neither.
III. S YSTEM M ODEL , D EFINITIONS , AND P RELIMINARIESIn this section, we present the system model for RD quantification. To provide consistency, we employ the same data
model, assumptions, and notations with existing quantification
work [5][9][10][11].
A. Data Model
Since we focus on structure-based de-anonymizability quantification, we model the anonymized data as a graph denotedby 𝐺𝑎 = (𝑉 𝑎 , 𝐸 𝑎 ), where 𝑉 𝑎 = {𝑖∣𝑖 is an anonymized user}
is the user set and 𝐸 𝑎 = {𝑒𝑎𝑖,𝑗 ∣𝑖, 𝑗 ∈ 𝑉 𝑎 } is the edge/link set[5][8][9][10][11]. To de-anonymize 𝐺𝑎 , we assume there is an
auxiliary graph 𝐺𝑢 = (𝑉 𝑢 , 𝐸 𝑢 ) available, where 𝑉 𝑢 = {𝑖∣𝑖is a known user} and 𝐸 𝑢 = {𝑒𝑢𝑖,𝑗 ∣𝑖, 𝑗 ∈ 𝑉 𝑢 } are the user andedge/link sets, respectively [5][8][9][10][11]. As indicated in[1][5][6][8][13], 𝐺𝑢 is widely available and can be obtained
through multiple means, e.g., online crawling, data aggregation, regular data publishing by companies and government
agencies, advertising, and third-party applications.
For facilitating our quantification, we restate the two assumptions in [5][8][9][10][11]. First, we assume 𝑉 𝑎 = 𝑉 𝑢although we do not know the exact mappings between theusers in 𝑉 𝑎 and 𝑉 𝑢 . Note that, this assumption does not
limit existing works [5][8][9][10][11] nor our quantification.
In the case that 𝑉 𝑎 ∕= 𝑉 𝑢 , we can simply make 𝑉 𝑎 = 𝑉 𝑢 byadding users in 𝑉 𝑢 ∖ 𝑉 𝑎 (resp., 𝑉 𝑎 ∖ 𝑉 𝑢 ) to 𝑉 𝑎 (resp. 𝑉 𝑢 )as isolated nodes (with degree of 0). Second, following thefirst assumption, we assume that 𝐺𝑎 and 𝐺𝑢 are two sampled
graphs of an underlaying conceptual graph 𝐺 = (𝑉, 𝐸),
where 𝑉 = 𝑉 𝑎 = 𝑉 𝑢 = {𝑖∣𝑖 is a physical user} and𝐸 = {𝑒𝑖,𝑗 ∣𝑖, 𝑗 ∈ 𝑉 } characterizes the possible real world
physical relationships (edges/links) among the users in 𝑉 . For
instance, given a group of people, their Facebook network
mainly carries their friendship relation while their LinkedIn
network mainly carries their career connections. Mathematically, this assumption can be formalized as ∀𝑒𝑖,𝑗 ∈ 𝐸,

Pr(𝑒𝑖,𝑗 ∈ 𝐸 𝑎 ) = 𝑠𝑎 and Pr(𝑒𝑖,𝑗 ∈ 𝐸 𝑢 ) = 𝑠𝑢 , where 𝑠𝑎 and𝑠𝑢 are the sampling probabilities of 𝐺𝑎 and 𝐺𝑢 , respectively.
Note that, the second assumption is only for the mathematical
purpose of conveniently quantifying the structural similarity
between 𝐺𝑎 and 𝐺𝑢 and does not limit the generality of ourquantification1 . Even without this assumption, the derivations
in [8][5][9][10][11] and this paper are still valid, however,they will be much more complicated (in that scenario, weneed to define more functions to characterize and calculate
the structural similarity between 𝐺𝑎 and 𝐺𝑢 ).
Now, we define some useful notations. We assume ∣𝑉 ∣ =𝑛 and ∣𝐸∣ = 𝑚. ∀𝑖 ∈ 𝑉 , we define its neighborhood anddegree as 𝑁𝑖 = {𝑗∣𝑒𝑖,𝑗 ∈ 𝐸} and 𝑑𝑖 = ∣𝑁𝑖 ∣, respectively.
Without loss of generality, we assume 𝑑𝑖 ≤ 𝑑𝑗 for 𝑖 < 𝑗,which implies 𝑑1 ≤ 𝑑2 ≤ ⋅ ⋅ ⋅ ≤ 𝑑𝑛 . ∀𝑈 ⊆ 𝑉 , we define𝑛𝑈 = ∣𝑈 ∣, 𝐸𝑈 = {𝑒𝑖,𝑗 ∈ 𝐸∣𝑖, 𝑗 ∈ 𝑈 } be the set of edges
among the users in 𝑈 , and 𝑚𝑈 = ∣𝐸𝑈 ∣. Furthermore, ∀𝑈 ⊆ 𝑉 ,we use 𝛿1𝑈 and 𝛿2𝑈 to denote its smallest and second smallest
𝑈
degrees of the users in 𝑈 , respectively, and use Δ𝑈
1 and Δ2
to denote its largest and second largest degrees of the users
in 𝑈 , respectively. For instance, when 𝑈 = 𝑉 , 𝛿1𝑈 = 𝑑1 ,𝑈
𝛿2𝑈 = 𝑑2 , Δ𝑈
1 = 𝑑𝑛 , and Δ2 = 𝑑𝑛−1 . Given 𝑈, 𝑊 ⊆ 𝑉 and𝑈 ∩𝑊 = ∅, we define the set of cross edges between 𝑈 and 𝑊
as 𝐸𝑈,𝑊 = {𝑒𝑖,𝑗 ∈ 𝐸∣𝑖 ∈ 𝑈, 𝑗 ∈ 𝑊 }, and 𝑚𝑈,𝑊 = ∣𝐸𝑈,𝑊 ∣.
To make our quantification general, as done in [5], we
assume 𝐺 follows the configuration model [12], under which
𝐺 can have an arbitrary degree sequence that follows any distribution. For ∀𝑖, 𝑗 ∈ 𝑉 , let 𝑝𝑖,𝑗 be the probability of an edge
existing between 𝑖 and 𝑗. Then, following the key property of𝑑𝑖 𝑑𝑗
𝑑 𝑖 𝑑𝑗≃.
the configuration model, we have 𝑝𝑖,𝑗 = 2𝑚−1
as 𝑚→∞ 2𝑚
For ∀𝑈 ⊆ 𝑉 , we define 𝑙𝑈 = min{𝑝𝑖,𝑗 ∣𝑖, 𝑗 ∈ 𝑈 } andℎ𝑈 = max{𝑝𝑖,𝑗 ∣𝑖, 𝑗 ∈ 𝑈 } be the minimum and maximum
existing probabilities of the edges in 𝐸𝑈 , respectively. Furthermore, given 𝑖 ∈ 𝑉 , 𝑈 ⊆ 𝑉 , and 𝑖 ∈/ 𝑈 , we define𝑙𝑖,𝑈 = min{𝑝𝑖,𝑗 ∣𝑗 ∈ 𝑈 } and ℎ𝑖,𝑈 = max{𝑝𝑖,𝑗 ∣𝑗 ∈ 𝑈 } bethe minimum and maximum existing probabilities of the edgesin 𝐸{𝑖},𝑈 .
In the following discussion of this paper, to minimize confusion, we use 𝑖, 𝑒𝑖,𝑗 , 𝑑𝑖 , 𝑁𝑖 , and other notations interchangeably
in the contexts of 𝐺, 𝐺𝑎 , and 𝐺𝑢 . For some specific scenarios,
we use superscripts ‘a’ and ‘u’ to distinguish between thecontexts of 𝐺𝑎 and 𝐺𝑢 , respectively.
B. Relative De-anonymizability
Now, we formally define RD. First, we formally define a DA
attack. Given 𝐺𝑎 and 𝐺𝑢 , a DA attack is defined as a mapping[5], [8], [9]: 𝜎 : 𝑉 𝑎 → 𝑉 𝑢 as shown in Fig.1 (which indicatesa mapping form 𝐺𝑎 to 𝐺𝑢 ), i.e., 𝜎 = {(𝑖, 𝜎(𝑖))∣𝑖 ∈ 𝑉 𝑎 }.
1 In practice, 𝐺𝑎 may be obtained by anonymizing the raw data using
any graph anonymization technique. Meanwhile, 𝐺𝑢 may be any specificauxiliary graph of the anonymized users. However, it is also reasonable toconsider 𝐺𝑎 and 𝐺𝑢 are correlated and structurally similar [2][5][9][15]. For
instance, if two users are connected on Facebook, they are also more likely
to be connected on LinkedIn compared to two arbitrary users without any
connection on Facebook. In consideration of this, we introduce and use theconceptual graph 𝐺 to simplify the characterization and formalization of thestructural similarity between 𝐺𝑎 and 𝐺𝑢 .

4

3
2
6

1

2'
5
Fig. 1.

4'

3'
1'
6'

5'

A DA attack.

Under 𝜎, ∀𝑖 ∈ 𝑉 𝑎 , 𝜎(𝑖) ∈ 𝑉 𝑢 ∪ {⊥}, where ⊥ is a special
not existing indicator. Furthermore, ∀𝑒𝑎𝑖,𝑗 ∈ 𝐸 𝑎 , let 𝜎(𝑒𝑎𝑖,𝑗 ) =𝑒𝜎(𝑖),𝜎(𝑗) and ∀𝑈 ⊆ 𝐸 𝑎 , 𝜎(𝑈 ) = {𝜎(𝑒𝑎𝑖,𝑗 )∣𝑒𝑎𝑖,𝑗 ∈ 𝑈 }. Since
we assume 𝑉 𝑎 = 𝑉 𝑢 , we define 𝑖 ∈ 𝑉 𝑎 is successfully deanonymized if 𝜎(𝑖) = 𝑖. Then, given a mapping 𝜎, we say it
is a 𝑘-error DA, denoted by 𝜎𝑘 , if there are 𝑘 users that areincorrectly de-anonymized, i.e., exists 𝑘 mappings (𝑖, 𝜎(𝑖)) in𝜎 such that 𝜎(𝑖) ∕= 𝑖. Specifically, when 𝑘 = 0, 𝜎0 is called
the perfect DA.
As we discussed before, in a given 𝐺, different users
have different structural importance for structural DA attacks.
Therefore, instead of treating all the users the same as donein previous quantifications [5][8][9][10][11], we study thisproblem under a more general context, where we quantify
the de-anonymizability of users adaptively according to theirrelative structural importance. According to the empiricalresults in [2], a user with a higher degree implies it has higher
structural importance, e.g., closeness centrality, betweenness
centrality [12]. Therefore, we measure users’ structural importance according to their degrees. Then, we define 𝐺’s 𝜃-RD
as follows.
Definition III.1. 𝜃-RD and 𝜃-relative DA. Given 𝐺, 𝐺𝑎 ,𝐺𝑢 and 𝜃 ∈ [0, 1], let 𝑉𝜃 = {𝑛, 𝑛 − 1, ⋅ ⋅ ⋅ , (1 − 𝜃)𝑛 + 1}
be the users in 𝐺 with top 𝜃𝑛 degrees (without loss ofgenerality, we assume 𝜃𝑛 is an integer value). Then, 𝐺𝑎 (orequivalently, 𝐺) is 𝜃-relatively de-anonymizable if all the users
in 𝑉𝜃 are perfectly de-anonymizable based on their structural
information carried by 𝐺𝑎 and 𝐺𝑢 . Furthermore, given 𝜎, if
all the users in 𝑉𝜃 are perfectly de-anonymized, 𝜎 is a 𝜃relative DA.
From the above definition, we can see that when 𝜃 = 0,
𝜃-RD turns to be the de-anonymizability definition consideredin [5][8]-[11]. Therefore, the quantification problem studied in[5][8]-[11] can be considered as a special case of 𝜃-relative
DA (we formally state this later). To make our quantification
more applicable, we also consider the scenario that 𝜎 tolerates
some DA error, indicated by 𝜖 ∈ [0, 𝜃], as follows.
Definition III.2. (𝜃, 𝜖)-RD and (𝜃, 𝜖)-relative DA. Given
𝐺, 𝐺𝑎 , 𝐺𝑢 , 𝜃, and 𝜖 ∈ [0, 𝜃], 𝐺𝑎 (or 𝐺) is (𝜃, 𝜖)-relative
de-anonymizable if at least (𝜃 − 𝜖)𝑛 users in 𝑉𝜃 can beperfectly de-anonymized based on their structural information.
Furthermore, 𝜎 is a (𝜃, 𝜖)-relative DA if at least (𝜃 −𝜖)𝑛 users
in 𝑉𝜃 are perfectly de-anonymized under 𝜎.
To measure the performance of a de-anonymization attack
𝜎, we use the edge difference between 𝐺𝑎 and 𝐺𝑢 under 𝜎 [5],[8], [9], which is defined as Ψ𝜎 = ∣𝜎(𝐸 𝑎 ) ∖ 𝐸 𝑢 ∣ + ∣𝜎 −1 (𝐸 𝑢 ) ∖𝐸 𝑎 ∣, i.e., Ψ𝜎 counts the number of edges that appeared in
one graph (𝐺𝑎 /𝐺𝑢 ) while not appearing in another graph(𝐺𝑢 /𝐺𝑎 ). Furthermore, ∀𝑈 ⊆ 𝐸, the edge difference between
𝐺𝑎 and 𝐺𝑢 associated with edges in 𝑈 under 𝜎 is defined as
Ψ𝜎:𝑈 = ∣𝜎(𝑈 𝑎 ) ∖ 𝑈 𝑢 ∣ + ∣𝜎 −1 (𝑈 𝑢 ) ∖ 𝑈 𝑎 ∣.
IV. S EED - BASED RD Q UANTIFICATION

in 𝑉𝜃 ∖ 𝑆, i.e., the 𝜃-RD of 𝐺𝑎 . Let ℰ 𝑠 be the event that there
is at least one incorrectly de-anonymized user in 𝑉𝜃 ∖ 𝑆. Then,
we have the following theorem.
Theorem 2. If 𝑠 >max

2ℎ𝑖 −𝑙𝑖 −𝑙𝑗

and Λ =𝑖∈𝑉𝜃 ∖𝑆,𝑗∈𝑉 ∖(𝑆∪{𝑖}) 2ℎ𝑖 −𝑙𝑖 ℎ𝑗 −𝑙𝑗 ℎ𝑖
2 ln 𝑛+ln 2𝜃𝑛Ω(), it is a.a.s. that Pr(ℰ 𝑠 ) → 0, i.e., 𝐺𝑎
𝑓𝑠𝑠
𝑛→∞

is

𝜃-relatively de-anonymizable.

In this section, we study the scenario that an adversary hassome seed knowledge. We denote the known seed set as 𝑆 ={𝑖∣𝑖 ∈ 𝑉, 𝑖 is a seed} and let Λ = ∣𝑆∣. For simplicity, we
first assume that 𝐺𝑎 and 𝐺𝑢 are sampled versions of 𝐺 withthe same sampling probability 𝑠, i.e., 𝑠𝑎 = 𝑠𝑢 = 𝑠. Then, we
extend our quantification to the case that 𝑠𝑎 ∕= 𝑠𝑢 .

ProofSketch:
Based
on
the
Boole’sin𝑠)≤equality
andTheorem
1,
we
have
Pr(ℰ
∑
Pr(𝑖 is incorrectly de-anonymized)≤
𝑖∈𝑉𝜃 ∖𝑆∑
2 exp(−Λ𝑓𝑠𝑠 ) ≤ 2𝜃𝑛 exp(−Λ𝑓𝑠𝑠 ) ≤ 𝑛12 . Then,

A. 𝜃-RD

according to thePr(ℰ 𝑠 ) → 0.

For ∀𝑖 ∈ 𝑉 ∖ 𝑆, let 𝑙𝑖 = 𝑙𝑖,𝑆 , ℎ𝑖 = ℎ𝑖,𝑆 . Define𝑠(𝑙𝑖 (1−ℎ𝑗 𝑠)+𝑙𝑗 (1−ℎ𝑖 𝑠)−2ℎ𝑖 (1−𝑠))2min
8(𝑙𝑖 (1−ℎ𝑗 𝑠)+𝑙𝑗 (1−ℎ𝑖 𝑠)+2ℎ𝑖 (1−𝑠)) . We

𝑓𝑠𝑠 =𝑖∈𝑉𝜃 ∖𝑆,𝑗∈𝑉 ∖(𝑆∪{𝑖})quantify the condition to de-anonymize a user given 𝑆 as
follows.
Theorem 1. For ∀𝑖 ∈ 𝑉 ∖ 𝑆, if 𝑠 >2ℎ𝑖 −𝑙𝑖 −𝑙𝑗max𝑗∈𝑉 ∖(𝑆∪{𝑖}) 2ℎ𝑖 −𝑙𝑖 ℎ𝑗 −𝑙𝑗 ℎ𝑖and Λ = Ω( 2 ln𝑓𝑛+1), then it is asymptotically almost surely𝑠𝑠2(a.a.s.) that 𝑖 is perfectly de-anonymizable given 𝑆.
Proof Sketch: ∀𝑣 ∈ 𝑆, Pr(𝑒𝑖,𝑣 ∈ 𝐸) = 𝑝𝑖,𝑣 under the configuration model. Furthermore, for mapping (𝑖, 𝑖), 𝑒𝑖,𝑣 causes
an edge difference if it is sampled into one graph (𝐺𝑎 /𝐺𝑢 )while not into the other (𝐺𝑢 /𝐺𝑎 ). Therefore, we have Pr(𝑒𝑖,𝑣induces one edge difference to mapping (𝑖, 𝑖)) = 2𝑝𝑖,𝑣 𝑠(1−𝑠).
Similarly, if 𝑖 is incorrectly de-anonymized to some 𝑗 ∕= 𝑖,then we have Pr(𝑒𝑖,𝑣 /𝑒𝑗,𝑣 induces one edge difference tomapping (𝑖, 𝑗)) = 𝑝𝑖,𝑣 𝑠(1 − 𝑝𝑗,𝑣 𝑠) + 𝑝𝑗,𝑣 𝑠(1 − 𝑝𝑖,𝑣 𝑠). Let
𝐸𝑖,𝑆 = {𝑒𝑖,𝑣 ∣𝑣 ∈ 𝑆}, 𝑋 be a random variable counting theedge differences for mapping (𝑖, 𝑖) caused by edges in 𝐸𝑖,𝑆 ,and 𝑌 be a random variable counting the edge differences formapping (𝑖, 𝑗 ∕=∑𝑖) caused by edges in 𝐸𝑖,𝑆 and 𝐸𝑗,𝑆 . Then,
B(1, 2𝑝𝑖,𝑣 𝑠(1 − 𝑠)) ≤ B(Λ, 2ℎ𝑖 𝑠(1 − 𝑠))we have 𝑋 ∼∑ 𝑣∈𝑆B(1, 𝑝𝑖,𝑣 𝑠(1 − 𝑝𝑗,𝑣 𝑠) + 𝑝𝑗,𝑣 𝑠(1 − 𝑝𝑖,𝑣 𝑠)) ≥and 𝑌 ∼𝑣∈𝑆

B(Λ, 𝑙𝑖 𝑠(1 − ℎ𝑗 𝑠) + 𝑙𝑗 𝑠(1 − ℎ𝑖 𝑠)), where B(⋅, ⋅) is a binomial
distribution. Let 𝜆𝑋 and 𝜆𝑌 be the mean values of 𝑋 and𝑝𝑖,𝑣 −𝑝𝑗,𝑣𝑌 , respectively. Since 𝑠 >max
2𝑝𝑖,𝑣 (1−𝑝𝑗,𝑣 ) , we𝑣∈𝑆,𝑗∈𝑉 ∖𝑆,𝑗∕=𝑖have 𝜆𝑌 > 𝜆𝑋 . Then, applying the Pedarsani-Grossglauser
2
𝑌 −𝜆𝑋 )
Lemma [9], we have Pr(𝑋 ≥ 𝑌 ) ≤ 2 exp(− (𝜆8(𝜆𝑋 +𝜆𝑌 ) ) ≤∑ 𝜋2
2 exp(−Λ𝑓𝑠𝑠 ) ≤ 2 exp(−2 ln 𝑛−1) ≤ 𝑛12 . Since
6 ≤ ∞,
𝑛≥1

according to the Borel-Cantelli Lemma, Pr(𝑋 ≥ 𝑌 ) →𝑛→∞
0 ⇔ Pr(𝑋 < 𝑌 ) → 1, i.e., 𝑖 is perfectly de-anonymizable𝑛→∞based on the edge difference relative to 𝑆.
□
Note that, the conclusion in Theorem 1 is valid not only
for any user in 𝑉𝜃 ∖ 𝑆 but also for any user in 𝑉 ∖ 𝑆. Now,
based on Theorem 1, we quantify a stronger conclusion, whichindicates the condition to perfectly de-anonymize all the users
2 Asymptotically almost surely (a.a.s.) implies that as 𝑛probability goes to 1 an event happens.

→ ∞, with𝑖∈𝑉𝜃 ∖𝑆

Borel-Cantelli

Lemma,

we

𝑛→∞

have
□

B. (𝜃, 𝜖)-RD
Now, we study the DA that tolerates some DA error, i.e., the(𝜃, 𝜖)-RD of 𝐺𝑎 . Let 𝑉𝜃−𝜖 = {𝑛, 𝑛 − 1, ⋅ ⋅ ⋅ , (1 + 𝜖 − 𝜃)𝑛 + 1}.
Then, we demonstrate the quantification in Theorem 3.
Theorem 3. If 𝑠 >2ℎ𝑖 −𝑙𝑖 −𝑙𝑗

max

and

𝑖∈𝑉𝜃−𝜖 ∖𝑆,𝑗∈𝑉 ∖(𝑆∪{𝑖}) 2ℎ𝑖 −𝑙𝑖 ℎ𝑗 −𝑙𝑗 ℎ𝑖
2 ln 𝑛+ln 2(𝜃−𝜖)𝑛Λ = Ω(), it is a.a.s. that 𝐺𝑎 is (𝜃, 𝜖)-relatively
𝑓𝑠𝑠de-anonymizable.

Proof Sketch: To prove this theorem, it is sufficient toquantify the condition under which there exists a perfectly deanonymizable subset of 𝑉𝜃 of size at least (𝜃 − 𝜖)𝑛. Here, we
consider 𝑉𝜃−𝜖 since the users in this set have higher structural
importance, i.e., they carry more structural information. Letℰ𝜖𝑠 be the event that there is at least one incorrectly deanonymized user in 𝑉𝜃−𝜖 . Thus, it is sufficient to prove that it
is a.a.s. Pr(ℰ𝜖𝑠 ) → 0. Then, based on similar arguments as𝑛→∞in Theorem 2, this theorem can be proven.
□
C. Extension: 𝑠𝑎 ∕= 𝑠𝑢
In the previous quantification, we assume 𝑠𝑎 = 𝑠𝑢 = 𝑠.
In reality, it is possible that 𝑠𝑎 ∕= 𝑠𝑢 . Now, we quantify
the 𝜃-RD and (𝜃, 𝜖)-RD of 𝐺𝑎 in this case. Let 𝑓𝑠𝑠𝑎 ,𝑠𝑢 =min𝑖∈𝑉𝜃 ∖𝑆,𝑗∈𝑉 ∖(𝑆∪{𝑖})((2ℎ𝑖 −𝑙𝑖 ℎ𝑗 −𝑙𝑗 ℎ𝑖 )𝑠𝑎 𝑠𝑢 +(𝑙𝑖 −ℎ𝑖 )𝑠𝑎 +(𝑙𝑗 −ℎ𝑖 )𝑠𝑢 )28((𝑙𝑖 +ℎ𝑖 )𝑠𝑎 +(𝑙𝑗 +ℎ𝑖 )𝑠𝑢 −(2ℎ𝑖 +𝑙𝑖 ℎ𝑗 +𝑙𝑗 ℎ𝑖 )𝑠𝑎 𝑠𝑢 ) .

We have the following theorem. The proof is omitted due to the space limitations.
𝑠𝑢>
Theorem 4. Suppose 𝑠𝑠𝑎𝑎+𝑠𝑢ℎ𝑖 −min{𝑙𝑖 ,𝑙𝑗 }2ℎ𝑖 −𝑙𝑖 ℎ𝑗 −𝑙𝑗 ℎ𝑖 .

max𝑖∈𝑉𝜃 ∖𝑆,𝑗∈𝑉 ∖(𝑆∪{𝑖})Λ = Ω( 2𝑓ln𝑠 𝑛+1 ), it
𝑠𝑎 ,𝑠𝑢Then, (𝑖) if
is a.a.s.
that 𝑖 is perfectly de-anonymizable given 𝑆; (𝑖𝑖) if Λ =2𝜃𝑛), it is a.a.s. that 𝐺𝑎 is 𝜃-relatively deΩ( 2 ln𝑓𝑛+ln𝑠
𝑠𝑎 ,𝑠𝑢2(𝜃−𝜖)𝑛anonymizable; and (𝑖𝑖𝑖) if Λ = Ω( 2 ln 𝑛+ln), it is a.a.s.
𝑓𝑠𝑠𝑎 ,𝑠𝑢𝑎that 𝐺 is (𝜃, 𝜖)-relatively de-anonymizable.

V. S EED - FREE RD Q UANTIFICATIONIn the previous section, we studied seed-based RD quantification. In this subsection, we study seed-free RD quantifica-

tion. Again, for simplicity, we first assume 𝑠𝑎 = 𝑠𝑢 = 𝑠 andthen extend to the case that 𝑠𝑎 ∕= 𝑠𝑢 .
A. 𝜃-RDLet 𝑙 = 𝑙𝑉 , 𝑙𝜃 = 𝑙𝑉𝜃 , ℎ𝜃 = ℎ𝑉𝜃 , 𝜅 = (1 − 𝜃)𝑛 and 𝜎𝜅 be a𝜃-relative DA. Furthermore, let 𝑘 ∈ [1, 𝜃𝑛] and 𝜎𝜅+𝑘 be a DA
such that 𝑘 users are incorrectly de-anonymized. Define 𝑓𝑠 =𝑠((𝑙+𝑙𝜃 )(1−ℎ𝜃 𝑠)−2ℎ𝜃 (1−𝑠))28((𝑙+𝑙𝜃 )(1−ℎ𝜃 𝑠)+2ℎ𝜃 (1−𝑠)) . We have the following theorem.
2 ln 𝑛+1𝜃 −𝑙𝜃 −𝑙and 𝑓𝑠 = Ω( 𝜃𝑘𝑛−𝑘Theorem 5. If 𝑠 > ℎ2ℎ
2 /2−𝑘 ), then𝜃 (2−𝑙𝜃 −𝑙)statistically, Pr(Ψ𝜎𝜅 < Ψ𝜎𝜅+𝑘 ) → 1, i.e., it is a.a.s. that a𝑛→∞𝜃-relative DA induces less edge difference than any DA which
incorrectly de-anonymizes some users in 𝑉𝜃 .

Proof Sketch: Let 𝐸𝑉𝜃 = 𝐸 ∖ 𝐸𝑉𝜃 . Then, according to theedge difference definition, we have Ψ𝜎 = Ψ𝜎:𝐸𝑉𝜃 + Ψ𝜎:𝐸𝑉𝜃
for any 𝜎. Since we only focus on de-anonymizing the users
in 𝑉𝜃 , statistically, to prove Pr(Ψ𝜎𝜅 < Ψ𝜎𝜅+𝑘 ) → 1, it is𝑛→∞sufficient to prove Pr(Ψ𝜎𝜅 :𝐸𝑉𝜃 < Ψ𝜎𝜅+𝑘 :𝐸𝑉𝜃 ) → 1. This is𝑛→∞because Ψ𝜎𝜅 :𝐸𝑉=Ψ𝜎𝜅+𝑘 :𝐸𝑉 .
𝜃𝑠𝑡𝑎𝑡𝑖𝑠𝑡𝑖𝑐𝑎𝑙𝑙𝑦,𝑛→∞𝜃

Let 𝑋 = Ψ𝜎𝜅 :𝐸𝑉𝜃 and 𝑌 = Ψ𝜎𝜅+𝑘 :𝐸𝑉𝜃 be two randomvariables. Furthermore, under 𝜎𝜅+𝑘 , let 𝐶 ⊂ 𝑉𝜃 and 𝐼 ⊆ 𝑉𝜃be the sets of users that are correctly and incorrectly deanonymized, respectively. Evidently, 𝐶 ∪ 𝐼 = 𝑉𝜃 , 𝐶 ∩ 𝐼 = ∅,and 𝐸𝑉𝜃 = 𝐸𝐶 ∪ 𝐸𝐼 ∪ 𝐸𝐶,𝐼 . For 𝑒𝑖,𝑗 ∈ 𝐸𝐼 , it is atransposition edge if (𝑖, 𝑗), (𝑗, 𝑖) ∈ 𝜎𝜅+𝑘 . Let 𝐸𝑡 = {𝑒𝑖,𝑗 ∣𝑒𝑖,𝑗
is a transposition edge under 𝜎(𝜅+𝑘) } and 𝑚𝑡 = ∣𝐸𝑡 ∣.( Then,)𝜃𝑛,𝑚𝑡 ≤ 𝑘/2. Let 𝑚𝜃 = ∣𝐸𝜃 ∣ = 𝑛2 , 𝑚𝐶 = ∣𝐸𝐶 ∣ = 𝜃𝑛−𝑘(𝑘 )𝑚𝐼 = ∣𝐸𝐼 ∣ = 2 , and 𝑚𝐶,𝐼 = ∣𝐸𝐶,𝐼 ∣ = 𝑘(𝜃𝑛 − 𝑘).
Now, ∀𝑒𝑖,𝑗 ∈ 𝐸𝑉𝜃 , it contributes one to 𝑋 if it is existedand∑sampled into exactly one of 𝐺𝑎 and 𝐺𝑢 . Thus, 𝑋 ∼B(1, 2𝑝𝑖,𝑗 𝑠(1 − 𝑠)). Similarly, ∀𝑒𝑖,𝑗 ∈ 𝐸𝐶 ∪ 𝐸𝑡 , it𝑒𝑖,𝑗 ∈𝐸𝑉𝜃

contributes one to 𝑌 if it is existed and sampled into exactly
one of 𝐺𝑎 and 𝐺𝑢 . ∀𝑒𝑖,𝑗 ∈ 𝐸𝐶,𝐼 ∪ (𝐸𝐼 ∖ 𝐸𝑡 ), it contributes
one to 𝑌 if 𝑒𝑖,𝑗 (or, 𝜎(𝑒𝑖,𝑗 )) is appeared in 𝐺𝑎 (or, 𝐺𝑢 ) while𝑢(or, 𝐺𝑎 ). Let 𝑞𝑖,𝑗 =𝜎(𝑒𝑖,𝑗 ) (or, 𝑒𝑖,𝑗 ) is not appeared in 𝐺∑
B(1, 2𝑝𝑖,𝑗 𝑠(1 −𝑝𝜎𝜅+𝑘 (𝑖),𝜎𝜅+𝑘 (𝑗) , we have 𝑌 ∼𝑒𝑖,𝑗 ∈𝐸𝐶 ∪𝐸𝑡∑𝑠))+
B(1, 𝑝𝑖,𝑗 𝑠(1−𝑞𝑖,𝑗 𝑠)+𝑞𝑖,𝑗 𝑠(1−𝑝𝑖,𝑗 𝑠)).
𝑒𝑖,𝑗 ∈𝐸𝐶,𝐼 ∪(𝐸𝐼∑∖𝐸𝑡 )Let 𝑋 ′ ∼B(1,𝑒𝑖,𝑗 ∈𝐸𝐶,𝐼 ∪(𝐸𝐼 ∖𝐸𝑡 )2𝑝𝑖,𝑗 𝑠(1 − 𝑠)) ∑≤ B(𝑚𝐶,𝐼 + 𝑚𝐼 − 𝑚𝑡 , 2ℎ𝜃 𝑠(1 − 𝑠)) andB(1, 𝑝𝑖,𝑗 𝑠(1 − 𝑞𝑖,𝑗 𝑠) + 𝑞𝑖,𝑗 𝑠(1 −𝑌′ ∼𝑒𝑖,𝑗 ∈𝐸𝐶,𝐼 ∪(𝐸𝐼 ∖𝐸𝑡 )TABLE IDATA STATISTICS .
Name
Google+LiveJournal
YouTube
Orkut
Pokec
Facebook
FlickrFoursquare
Twitter
GowallaAstroPh
Enron
EuAll
Skitter
Gnutella𝑛4,692,671
4,847,571
1,134,890
3,072,441
1,632,803
63,73180,513
639,014456,631
196,591
18,772
36,692
265,214
1,696,415
26,518

Type
SN
SN
SN
SN
SN
SN
SN
SN
SN
LSN
Collab.
Email
Email
AS
P2P

𝑚
90,751,480
68,993,773
2,987,624
117,185,083
30,622,564
817,0905,899,882
3,214,986
14,855,875
950,327
396,160
183,831420,045
11,095,298
65,369𝜌
8.24E-6
3.70E-6
4.64E-6
2.48E-5
1.67E-5
4.02E-4
1.82E-3
1.57E-5
1.20E-4
4.92E-5
1.23E-3
3.19E-4
1.35E-5
7.73E-6
1.86E-4

𝑑
38.7
17.9
5.3
76.3
27.3
25.6
146.6
10.1
54.8
9.7
22.0
10.7
3.0
13.1
4.9

Pr(Ψ𝜎𝜅 < Ψ𝜎𝜅+𝑘 ) for any 𝜎𝜅+𝑘 . Now, we quantify the 𝜃RD of 𝐺𝑎 . To achieve this, statistically, we need to show theuniqueness of 𝜎𝜅 , i.e., ∄𝜎𝜅+𝑘 such that Ψ𝜎𝜅+𝑘 ≤ Ψ𝜎𝜅 . We
give the quantification in Theorem 6. The proof is omitted
due to the space limitations.
2ℎ𝜃 −𝑙𝜃 −𝑙ℎ𝜃 (2−𝑙𝜃 −𝑙)and 𝑓𝑠=2 ln 𝑛+(𝑘+1) ln 𝜃𝑛+1
Ω( 𝜃𝑘𝑛−𝑘2 /2−𝑘 ), then statistically, it is a.a.s. that
∄𝜎𝜅+𝑘 such that Ψ𝜎𝜅+𝑘 ≤ Ψ𝜎𝜅 , i.e., it is a.a.s. that 𝐺𝑎 is

Theorem

6.

If

𝑠

>

𝜃-relatively de-anonymizable.
B. (𝜃, 𝜖)-RD

Now, we study the RD of 𝐺𝑎 when some error is tolerated.
We show the quantification in Theorem 7, where the proof isomitted due to the space limitations.
2ℎ

−𝑙

−𝑙

𝜃−𝜖
Theorem 7. If 𝑠 > ℎ𝜃−𝜖𝜃−𝜖(2−𝑙𝜃−𝜖 −𝑙) and 𝑓𝑠 =𝑛+(𝑘+1) ln(𝜃−𝜖)𝑛+1), it is a.a.s. that 𝐺𝑎 is (𝜃, 𝜖)Ω( 2 ln (𝜃−𝜖)𝑘𝑛−𝑘
2 /2−𝑘relatively de-anonymizable.

C. Extension: 𝑠𝑎 ∕= 𝑠𝑢
In Theorems 5, 6, and 7, we consider the casethat 𝑠𝑎 = 𝑠𝑢 . When 𝑠𝑎 ∕= 𝑠𝑢 , let 𝑓𝑠𝑎 ,𝑠𝑢 =((2−𝑙−𝑙𝜃 )ℎ𝜃 𝑠𝑎 𝑠𝑢 +(𝑙𝜃 −ℎ𝜃 )𝑠𝑎 +(𝑙−ℎ𝜃 )𝑠𝑢 )28((𝑙𝜃 +ℎ𝜃 )𝑠𝑎 +(𝑙+ℎ𝜃 )𝑠𝑢 −(2+𝑙+𝑙𝜃 )ℎ𝜃 𝑠𝑎 𝑠𝑢 ) . We quantify the RD of
𝐺𝑎 as follows. The proof is omitted due to the space limitations.
ℎ𝜃 −𝑙𝑠𝑢> ℎ𝜃 (2−𝑙andTheorem 8. Statistically, (𝑖) if 𝑠𝑠𝑎𝑎+𝑠𝑢𝜃 −𝑙)
2 ln 𝑛+1
𝑓𝑠𝑎 ,𝑠𝑢 = Ω( 𝜃𝑘𝑛−𝑘2 /2−𝑘 ), Pr(Ψ𝜎𝜅 < Ψ𝜎𝜅+𝑘 ) → 1; (𝑖𝑖)𝑛→∞𝑝𝑖,𝑗 𝑠)) ≥ B(𝑚𝐶,𝐼 +𝑚𝐼 − 𝑚𝑡 , 𝑠(𝑙 + 𝑙𝜃 )(1 − ℎ𝜃 𝑠)). Thus,
Pr(𝑋 < 𝑌 ) = Pr(𝑋 ′ < 𝑌 ′ ). Let 𝜆𝑋 ′ and 𝜆𝑌 ′ be the mean
𝜃 −𝑙,values of 𝑋 ′ and 𝑌 ′ , respectively. Then, since 𝑠 > ℎ𝜃ℎ(1−𝑙)𝜆𝑋 ′ < 𝜆𝑌 ′ . Thus, based on the Pedarsani-Grossglauser
2
𝑌 ′ −𝜆𝑋 ′ )Lemma [9], Pr(𝑋 ′ ≥ 𝑌 ′ ) ≤ 2 exp(− (𝜆8(𝜆𝑋 ′ +𝜆𝑌 ′ ) ) ≤ 2 exp(−(𝜃𝑘𝑛 − 𝑘 2 /2 − 𝑘)𝑓𝑠 ) ≤ 2 exp(−2 ln 𝑛 − 1) ≤ 𝑛12 . Thus,
according to the Borel-Cantelli Lemma, Pr(𝑋 ′ ≥ 𝑌 ′ ) → 0,𝑛→∞=Pr(Ψ𝜎𝜅 <i.e., Pr(𝑋 ′ < 𝑌 ′ ) = Pr(𝑋 < 𝑌 )𝑛+(𝑘+1) ln(𝜃−𝜖)𝑛+1), it is a.a.s. that 𝐺𝑎 is (𝜃, 𝜖)Ω( 2 ln (𝜃−𝜖)𝑘𝑛−𝑘
2 /2−𝑘relatively de-anonymizable.

□
Ψ𝜎𝜅+𝑘 ) → 1.
𝑛→∞
In theorem 5, we quantified the condition such that

To validate our quantification techniques, we employ 15 realworld graph datasets (which are obtained from Stanford SNAP[16]/ASU Data Repository [17], and have been used in the𝑠𝑡𝑎𝑡𝑖𝑠𝑡𝑖𝑐𝑎𝑙𝑙𝑦,𝑛→∞ln 𝜃𝑛+1ℎ𝜃 −𝑙𝑠𝑢
if 𝑠𝑠𝑎𝑎+𝑠> ℎ𝜃 (2−𝑙and 𝑓𝑠𝑎 ,𝑠𝑢 = Ω( 2 ln 𝑛+(𝑘+1)),𝜃𝑘𝑛−𝑘2 /2−𝑘𝑢𝜃 −𝑙)
it is a.a.s. that 𝐺𝑎 is 𝜃-relatively de-anonymizable;𝑠𝑢
𝜃−𝜖 −𝑙> ℎ𝜃−𝜖ℎ(2−𝑙and 𝑓𝑠𝑎 ,𝑠𝑢 =and (𝑖𝑖𝑖) if 𝑠𝑠𝑎𝑎+𝑠𝑢
𝜃−𝜖 −𝑙)VI. L ARGE - SCALE E VALUATION
A. Datasetslatest quantification work [5], [8]) as shown in Table I, where𝑛 indicates the number of nodes (users), 𝑚 is the number ofedges (links/relationships), 𝜌 is the graph density, and 𝑑 is theaverage degree of each node. The 15 datasets are generated
from various computer systems/services. We briefly introduce
the datasets as follows.
∙ Social Network Graph (SN). Google+ is a social
networking and identity service that is owned and operated by
Google. LiveJournal is a social networking service where users
can keep a blog, journal, or diary. YouTube is a popular videosharing service/website where users can share their videos withfriends, family, and the world. Orkut is a social networking
service which is designed to help users meet new and oldfriends and maintain existing relationships. Pokec is one of
the most popular online social networking services in Slovakia.
Facebook is one of the most popular online social networking
services in the world, where users can create their profiles, add
other as “friends”, exchange messages, post status updates andphotos, share videos, and receive notifications when others
update their profiles. Flickr is an image and video hosting
website/social network service. Foursquare is a local searchand discovery mobile service which provides a personalized
local search experience for its users. Twitter is an online social
networking service that enables users to send and read short
140-character messages called “tweets”.
∙ Location-based Social Network (LSN) Graph. Gowalla
is a location-based social networking service, where users areable to check in at “Spots” in their local vicinity, either througha dedicated mobile application or through the mobile website.
∙ Collaboration (Collab.) Graph. AstroPh is from the e-print
arXiv and covers scientific collaborations between authorspapers submitted to the Astro Physics category.
∙ Email Graph. Enron is an email graph that was originallymade public and posted to the web by the Federal Energy
Regulatory Commission during its investigation. EuAll is anemail graph that was generated using the email data from alarge European research institution.
∙ Autonomous System (AS) Graph. Skitter is an Internet
topology graph.
∙ P2P Graph. Gnutella is the network topology graph of
the P2P network Gnuttella.
B. Evaluation Methodology
To ensure that our results can be fairly compared with thosein [5], [8], we use the same evaluation setup as in [5], [8], i.e.,
we do not preprocess the employed datasets, e.g., removing
low-degree users. Furthermore, as in [5], [8], we assume 𝑠𝑎 =𝑠𝑢 = 𝑠 for convenience. Note that this assumption does not
limit the generality of our evaluation. All the evaluations canbe extended to the case of 𝑠𝑎 ∕= 𝑠𝑢 directly.
In our evaluation, we mainly focus on evaluating the impactsof 𝜃 and 𝑠 on the inherent de-anonymizability of each dataset
using our quantifications in Section IV and Section V, i.e., howtheoretically de-anonymizable the users of each dataset arewith respect to their structural properties. Let Ξ be a DA attack
without any computational limitation and Ξ de-anonymizes 𝐺𝑎

leveraging 𝐺𝑢 by minimizing the edge difference function Ψ𝜎defined in Section III. Therefore, the output DA scheme of Ξis the mapping scheme 𝜎 ∗ such that 𝜎 ∗ = arg min Ψ𝜎 , i.e.,𝜎𝜎 ∗ has the minimum edge difference among all the possible
DA schemes3 . Then, statistically, each evaluation result in thissection can be considered as the performance lower bound of
Ξ under a specific setting of 𝜃 and 𝑠.
C. Seed-based RD Evaluation
In this subsection, we evaluate the seed-based RD of the 15
datasets. The number of available seeds is assumed to be 50,
i.e., Λ = 50. To simplify the evaluation process, we take theusers with the top-50 degrees in each dataset as the seeds.
1) RD versus 𝜃: When 𝑠 = 0.6 and Λ = 50, we evaluate
the seed-based RD of each dataset with respect to different 𝜃 asshown in Table II, where each value indicates the percentage
of users that can be successfully de-anonymized. From Table
II, we have the following observations.
When 𝜃 increases, the seed-based RD of each dataset decreases. For instance, when 𝜃 = 0.05 (i.e., the target DA users
are the top-5% users with respect to degree), 100% of target
users of Google+ can be successfully de-anonymized, while
when 𝜃 = 0.45 (the target users now are the top-45% users
with respect to degree), the successfully de-anonymizable
target users of Google+ are decreased to 60.1%. The reason
is that when 𝜃 increases, more users with relatively low
degrees become target users of DA. However, less structural
information is available for the the new considered low-degree
users, and thus the RD of each dataset decreases.
Generally, the datasets with higher average degree (i.e., 𝑑)and graph density (i.e., 𝜌) are more de-anonymizable than thedatasets with lower average degree and graph density. For
instance, as shown in Table I, Google+ has a similar sizewith LiveJournal. However, Google+ has a higher average
degree/graph density than LiveJournal. According to Table
II, Google+ is more de-anonymizable than LiveJournal, e.g.,when 𝜃 = 0.3, 94.6% target users of Google+ can be deanonymized while 57.2% target users of LiveJournal can bede-anonymized. This is because Google+ has a larger 𝑑/𝜌,and thus more structural information is available to uniquely
and correctly distinguish the users in Google+ compared to
LiveJournal.
2) RD versus 𝑠: When 𝜃 = 0.5, the seed-based deanonymizability of the 15 datasets under different 𝑠 is shownin Table III, where each value indicates the percentage of target
users that can be successfully de-anonymized. From Table III,
we have the following observations.
When 𝑠 increases, more users can be successfully deanonymized. For instance, when 𝑠 = 0.4, 23.7% of thetarget users of Google+ can be successfully de-anonymized
and when 𝑠 = 0.7, the ratio of target users that can be
3 Given 𝐺𝑎 and 𝐺𝑢 , it is intuitively that there are at most 𝑛! possible DA
schemes, i.e., at most 𝑛! mapping schemes from 𝑉 𝑎 to 𝑉 𝑢 . Then, if there isno computational limitation on Ξ, Ξ can minimize Ψ𝜎 by examining all the𝑛! possible DA schemes.

TABLE II
S EED - BASED DE - ANONYMIZABILITY ANALYSIS (𝑠 = .6, Λ = 50).
𝜃=Google+LiveJournal
YouTube
Orkut
Pokec
Facebook
FlickrFoursquare
Twitter
GowallaAstroPh
Enron
EuAll
Skitter
Gnutella

.05
100%
100%
100%
100%
100%
100%
100%
100%
100%
100%
99.9%
99.9%
100%
100%
99.5%

.1
100%
100%
98.1%
100%
100%
100%
100%
100%
100%
100%
99.9%
99.9%
79.0%
100%
71.7%

.15
100%
100%
64.5%
100%
100%
100%
100%
99.9%
100%
93.4%
99.9%
99.8%
52.0%
100%
48.6%

.2
100%
88.7%
47.6%
100%
100%
100%
100%
76.4%
100%
69.0%
99.7%
84.8%
38.5%
76.6%
36.9%

.25
100%
69.8%
37.5%
100%
87.3%
99.6%
100%
60.2%
100%
54.3%
95.3%
66.8%
30.3%
60.4%
29.9%

.3
94.6%
57.2%
30.8%
100%
71.4%
84.6%
100%
49.4%
100%
44.5%
78.7%
54.8%
24.9%
49.5%
25.3%

.35
79.8%
48.2%
26.0%
100%
60.0%
71.2%
100%
41.7%
100%
37.5%
66.2%
46.2%
21.0%
41.7%
22.0%

.4
68.7%
41.4%
22.3%
98.5%
51.5%
61.2%
100%
35.8%
93.7%
32.2%
56.8%
39.8%
18.1%
35.9%
19.4%

.45
60.1%
36.1%
19.5%
86.0%
44.9%
53.3%
100%
31.3%
81.9%
28.1%
49.5%
34.8%
15.8%
31.3%
17.5%

.7
74.0%
45.1%
23.6%
100%
58.1%
68.2%
100%
38.0%
100%
34.9%
64.4%
42.5%
18.7%
38.4%
22.6%

.75
86.3%
52.9%
27.2%
100%
69.2%
80.5%
100%
43.8%
100%
40.8%
76.5%
49.4%
21.4%
44.7%
26.8%

.4
56.8%
31.2%
16.6%
85.0%
38.7%
48.6%
100%
27.4%
82.2%
24.1%
44.3%
31.1%
13.7%
27.3%
14.0%

.45
52.9%
29.5%
15.6%
79.4%
36.7%
45.8%
100%
25.7%
76.3%
22.7%
41.9%
29.1%
12.8%
25.7%
13.8%

TABLE IIIS EED - BASED DE - ANONYMIZABILITY ANALYSIS (𝜃 = .5, Λ = 50).
𝑠=
Google+LiveJournal
YouTube
Orkut
Pokec
Facebook
FlickrFoursquare
Twitter
GowallaAstroPh
Enron
EuAll
Skitter
Gnutella

.35
18.4%
9.9%
6.1%
21.5%
10.5%
12.3%
46.7%
9.3%
23.6%
7.9%
9.6%
9.7%
5.4%
9.5%
7.2%

.4
23.7%
13.2%
7.9%
29.1%
14.5%
17.4%
62.3%
12.2%
31.0%
10.5%
14.8%
13.1%
6.8%
12.3%
8.3%

.45
29.7%
17.0%
9.8%
38.2%
19.4%
23.3%
80.2%
15.4%
39.5%
13.4%
20.5%
16.9%
8.4%
15.5%
9.6%

.5
36.6%
21.3%
12.0%
48.9%
25.2%
30.2%
99.5%
19.1%
49.1%
16.8%
27.2%
21.0%
10.1%
19.1%
11.3%

.55
44.4%
26.3%
14.5%
61.5%
31.8%
38.1%
100%
23.1%
60.1%
20.6%
34.9%
25.6%
11.9%
23.2%
13.4%

.6
53.2%
31.9%
17.2%
76.0%
39.5%
47.1%
100%
27.7%
72.5%
24.8%
43.6%
30.7%
14.0%
27.7%
16.0%

.65
63.0%
38.2%
20.3%
92.5%
48.3%
57.1%
100%
32.6%
86.4%
29.6%
53.4%
36.3%
16.3%
32.8%
19.0%

TABLE IVS EED - FREE DE - ANONYMIZABILITY ANALYSIS (𝑠 = .6).
𝜃=
Google+LiveJournal
YouTube
Orkut
Pokec
Facebook
FlickrFoursquare
Twitter
GowallaAstroPh
Enron
EuAll
Skitter
Gnutella

.05
100%
94.0%
51.7%
100%
99.9%
99.7%
100%
89.5%
100%
73.2%
96.3%
97.1%
46.4%
91.1%
18.7%

.1
100%
63.6%
34.8%
100%
73.3%
98.3%
100%
59.0%
100%
49.6%
85.0%
68.6%
30.4%
59.3%
17.4%

.15
100%
51.3%
27.9%
100%
60.6%
81.3%
100%
46.8%
100%
39.9%
70.7%
54.1%
23.9%
46.8%
16.4%

.2
87.4%
44.2%
23.9%
100%
53.0%
69.8%
100%
39.9%
100%
34.3%
61.7%
45.9%
20.2%
39.8%
15.7%

successfully de-anonymized is increased to 74%. This isbecause a large 𝑠 implies more common edges are shared by
𝐺𝑎 (the anonymized graph) and 𝐺𝑢 (the auxiliary graph), i.e.,
more structural similarity between 𝐺𝑎 and 𝐺𝑢 . Hence, moreusers in 𝐺𝑎 can be successfully de-anonymized leveraging theincreased structural similarity between 𝐺𝑎 and 𝐺𝑢 .
Even if 𝑠 is small, a significant number of users withineach dataset can still be successfully de-anonymized, e.g.,
18.4% target users of Google+ and 46.7% target users of
Flickr can be successfully de-anonymized when 𝑠 = 0.35.

.25
75.8%
39.5%
21.2%
100%
47.9%
62.1%
100%
35.4%
100%
30.6%
55.5%
40.4%
17.8%
35.2%
15.1%

.3
67.7%
36.0%
19.3%
100%
44.1%
56.4%
100%
32.0%
99.1%
27.9%
50.8%
36.5%
16.1%
31.9%
14.7%

.35
61.6%
33.4%
17.8%
91.9%
41.1%
52.1%
100%
29.4%
89.7%
25.8%
47.2%
33.5%
14.7%
29.3%
14.3%

This demonstrates that structure-based DA is very powerful.
Therefore, in addition to protect the semantic information
carried by graph data, the data’s structural information is also
important and deserves dedicated consideration/protection.
Similar to analyze Table II, if a dataset has higher average degree and/or graph density, it is more vulnerable tostructure-based DA attacks, e.g., Flickr is more vulnerable than
Google+. The reason is the same as analyzed before: higher
average degree and/or graph density imply more structural
information can be used for conducting successful DA.

TABLE V
S EED - FREE DE - ANONYMIZABILITY ANALYSIS (𝜃 = .5).
𝑠=Google+LiveJournal
YouTube
Orkut
Pokec
Facebook
FlickrFoursquare
Twitter
GowallaAstroPh
Enron
EuAll
Skitter
Gnutella

.35
15.8%
8.1%
5.1%
18.0%
8.3%
9.8%
43.1%
7.7%
20.5%
6.5%
6.5%
7.9%
4.5%
7.9%
6.5%

.4
20.6%
10.9%
6.5%
25.0%
11.7%
14.2%
60.1%
10.2%
27.4%
8.7%
11.6%
10.9%
5.8%
10.3%
7.4%

.45
26.3%
14.2%
8.2%
33.7%
16.0%
19.7%
80.8%
13.0%
35.7%
11.2%
16.9%
14.4%
7.1%
13.1%
8.5%

.5
32.9%
18.1%
10.2%
44.7%
21.2%
26.2%
99.9%
16.4%
45.7%
14.2%
23.2%
18.2%
8.6%
16.4%
9.8%

.55
40.7%
22.7%
12.3%
58.2%
27.5%
34.1%
100%
20.1%
57.5%
17.6%
30.8%
22.6%
10.3%
20.1%
11.5%

.6
49.8%
28.0%
14.8%
74.8%
35.0%
43.4%
100%
24.3%
71.3%
21.6%
39.8%
27.5%
12.1%
24.3%
13.6%

.65
60.3%
34.1%
17.5%
94.8%
44.0%
54.2%
100%
29.2%
87.6%
26.1%
50.4%
33.1%
14.1%
29.1%
16.0%

.7
72.6%
41.2%
20.6%
100%
54.6%
66.8%
100%
34.5%
100%
31.2%
62.8%
39.4%
16.3%
34.7%
19.1%

.75
86.9%
49.2%
24.0%
100%
67.1%
81.3%
100%
40.5%
100%
37.1%
77.0%
46.5%
18.8%
41.0%
22.9%

D. Seed-free RD Evaluation
1) RD versus 𝜃: When we fix 𝑠 = 0.6, the seed-free RD of
the 15 datasets given different 𝜃 is shown in Table IV. From
Table IV, we have the following observations.
Generally, all the datasets are completely or partially deanonymizable even if there is no seed information available,i.e., the considered graph datasets are completely/partially deanonymizable based only on their structural information. For
instance, when 𝜃 = 0.3, 94.6%, 84.6%, and 100% target usersof Google+, Facebook, and Twitter can be successfully deanonymized, respectively. This is because, as shown in ourde-anonymizability quantification, the structural information
associated with users (especially high-degree users) is sufficient to uniquely distinguish them with a high probability.
Therefore, our seed-free RD quantification provides the theoretical foundation for the success of emerging seed-free DA
attacks, e.g., Bayesian-based attack [4] and optimization-based
attack [5].
When 𝜃 increases, the target users of each dataset (except
for Flickr) become less de-anonymizable. For instance, 69.8%
target users of Facebook are de-anonymizable when 𝜃 = 0.2
while 48.6% target users of Facebook are de-anonymizable
when 𝜃 = 0.4. The reason is the same as analyzed in the seedbased DA scenario: with the increase of 𝜃, more relatively
low-degree users become to target DA users. However, lessstructural information can be employed to de-anonymize therelatively low-degree users, followed by the decrease of thepercentage of the de-anonymizable users in each dataset.
When comparing the results in Table IV (the seed-freescenario) with the results in Table II (the seed-based scenario),
we find that each dataset is more de-anonymizable in the seedbased scenario than that in the seed-free scenario, which isconsistent with the intuition given the same 𝜃. For instance,
when 𝜃 = 0.3, 84.6% target users of Facebook can be
successfully de-anonymized in the seed-based DA scenario
while 56.4% target users of Facebook can be successfully deanonymized in the seed-free DA scenario. Therefore, although
the carried structural information of graph data is sufficient
to conduct large-scale successful DA, we conclude that theavailable seed information can improve the DA performance.

(a) SBRD vs SBD (Λ = 50)(b) SFRD vs CCS’14
Fig. 2.

Comparisons with state-of-the-art quantification techniques [5], [8].

Similar to the seed-based DA scenario, if a dataset has
higher average degree and/or graph density, it is also more deanonymizable in the seed-free DA scenario. Again, the reason
is due to the carried richer structural information.
2) RD versus 𝑠: When fixing 𝜃 = 0.5, the seed-free RD of
the 15 datasets with respect to different 𝑠 is shown in TableV, from which we have the following observations.
Similar to the seed-based DA scenario, with the increaseof 𝑠, all the datasets become more de-anonymizable. For
instance, when 𝑠 = 0.35, 15.8% target users of Google+ canbe successfully de-anonymized while when 𝑠 = 0.75, 86.9%
target users of Google+ can be successfully de-anonymized.
The reason is also the same as in the seed-based DA scenario:

a large 𝑠 implies 𝐺𝑎 is more structurally similar to 𝐺𝑢 , andthus more users in 𝐺𝑎 can be successfully de-anonymized
leveraging 𝐺𝑢 .
When comparing Table V (the seed-free scenario) with
Table III (the seed-based scenario), we find that each dataset
is more de-anonymizable when having seed information available. For instance, when 𝑠 = 0.5, 49.1% target users ofTwitter can be successfully de-anonymized in the seed-based
DA scenario while 45.7% target users of Twitter can be
successfully de-anonymized in the seed-free DA scenario.
Again, the reason is straightforward: the available seed users
can provide more accurate auxiliary information in the DA.
Due to the same reason as analyzed before, the datasetswith the higher average degree and/or graph density are morede-anonymizable than the datasets with lower average degree
and/or graph density.
E. Comparisons with State-of-the-Art Quantifications
In this subsection, we experimentally compare our SeedBased RD quantification (SBRD) with the state-of-the-art
seed-based de-anonymizability quantification technique in[8], denoted by SBD, and compare our Seed-Free RD
quantification (SFRD) with the state-of-the-art seed-free deanonymizability quantification technique in [5], denoted by
SFD. Since the common datasets employed in [5], [8], andthis paper are Google+, LiveJournal, Orkut, Twitter, Gowalla,
Enron, and Skitter, we employ these 7 datasets to conduct
the comparative evaluation study. When comparing SBD and
SBRD, we select 50 top-degree users from each dataset toserve as seeds. Furthermore, in all the evaluation, we set
𝑠 = 𝑠𝑎 = 𝑠𝑢 = 0.6 for convenience.
Leveraging the 7 datasets, we show the seed-based deanonymizability evaluation results of SBD and SBRD in
Fig.2 (a) and show the seed-free de-anonymizability evaluation
results of SFD and SFRD in Fig.2 (b). From Fig.2, we makethe following observations.
When comparing SBD with SBRD (Fig.2 (a)), we findthat all the 7 datasets are actually more de-anonymizable
under SBRD that under SBD. Therefore, the results implies
the seed-based DA conditions obtained in this paper are
more accurate/tighter than that in [8]. The reason is because
instead of considering all the users structurally equivalent, we
adaptively quantify the de-anonymizability of users according
to their structural importance.
Similarly, when comparing SFD and SFRD (Fig.2 (b)), all
the datasets are more de-anonymizable under SFRD than under
SFD, which implies our seed-free RD quantification technique
is more accurate than that in [5]. The reason is the same asin the seed-based de-anonymizability quantification scenario:
adaptively considering users’ structural importance enables us
to quantify the de-anonymizability of graph data in a moreaccurate manner.
Remark. For sparse graph datasets (e.g., LiveJournal), theimprovements of our relative quantifications are not verysignificant compared with state-of-the-art quantifications. Thisis because less structural information is carried by sparsegraphs, i.e., they are inherently more resistant to structurebased DA attacks. The most notable contribution of our RD
quantifications is that we fundamentally/theoretically provide
more accurate/tighter seed-based and seed-free DA bounds foranonymized graph data than state-of-the-art quantifications.
VII. C ONCLUSION
In this paper, we study the structural importance-aware RD
quantification problem for graph data. Specifically, we quantify both the seed-based and the seed-free RD of anonymized
graph data for both perfect DA (de-anonymizing all the target
users) and partial de-anonymizaiton (tolerating some DA error)
under a general graph model. In our quantification, instead oftreating all the users in a graph dataset as structurally equivalent, we adaptively quantify their actual de-anonymizability
in terms of their structural importance. Leveraging 15 realworld graph datasets, we evaluate our relative quantifications
and compare them with state-of-the-art seed-based and seedfree quantification techniques. The results demonstrate that our
structural importance-aware relative quantifications are moreaccurate when measuring graph data’s real de-anonymizability.
ACKNOWLEDGMENT
This work was supported in part by NSF awards number
CNS-1409415 and CNS-1423139.
R EFERENCES[1] A. Narayanan and V. Shmatikov. De-anonymizing social networks. S&P,
2009.
[2] S. Ji, W. Li, M. Srivatsa, J. He, and R. Beyah. Structure based datade-anonymization of social networks and mobility traces. ISC, 2014.
[3] L. Backstrom, C. Dwork, and J. Kleinberg. Wherefore art thour3579x? anonymized social networks, hidden patterns, and structuralsteganography. WWW, 2007.
[4] P. Pedarsani, D. R. Figueiredo, and M. Grossglauser. A bayesian method
for matching two similar graphs without seeds. Allerton, 2013.
[5] S. Ji, W. Li, M. Srivatsa, and R. Beyah.
Structural data deanonymization: Quantification, practice, and implications. CCS, 2014.
[6] M. Srivatsa and M. Hicks. Deanonymizing mobility traces: Using social
networks as a side-channel. CCS, 2012.
[7] 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. USENIX Security, 2015.
[8] S. Ji, W. Li, N. Gong, P. Mittal, and R. Beyah. On your social network
de-anonymizablity: Quantification and large scale evaluation with seedknowledge. NDSS, 2015.
[9] P. Pedarsani and M. Grossglauser. On the privacy of anonymized
networks. KDD, 2011.
[10] L. Yartseva and M. Grossglauser. On the performance of percolationgraph matching. COSN, 2013.
[11] N. Korula and S. Lattanzi. An efficient reconciliation algorithm forsocial networks. VLDB, 2014.
[12] M. E. J. Newman. Networks: An introduction. Oxford University Press,
2010.
[13] A. Narayanan, E. Shi, and B. Rubinstein. Link prediction by deanonymization: How we won the kaggle social network challenge.
IJCNN, 2011.
[14] S. Nilizadeh, A. Kapadia, and Y.-Y. Ahn. Community-enhanced deanonymization of online social networks. CCS, 2014.
[15] P. Mittal, C. Papamanthou, and D. Song. Preserving link privacy insocial network based systems. NDSS 2013.
[16] Stanford
Large
Network
Dataset
Collection.
http://snap.stanford.edu/data/index.html.
[17] ASU
SocialComputing
Data
Repository.
http://socialcomputing.asu.edu/pages/datasets.