DEIM Forum 2013 E4-3

An Improved Label-bag based Graph Anonymization based on Utility
李重頡†

天笠 俊之†

北川 博之†

GautamSrivastava††† 筑波大学大学院システム情報工学研究科 〒 305–8573 つくば市天王台 1-1-1†† Dept of Computer Science, University of Victoria
Victoria, BC Canada
E-mail: †lichongjie@kde.cs.tsukuba.ac.jp, ††amagasa@cs.tsukuba.ac.jp, †††kitagawa@cs.tskuba.com,††††gsrivast@uvic.ca

An Improved Label-bag based Graph Anonymization based on Utility
Chongjie LI† , Toshiyuki AMAGASA† , Hiroyuki KITAGAWA† , and Gautam SRIVASTAVA††† Graduate School of Information Engineering, University of Tsukuba
1-1-1 Tennodai, Tsukuba, Ibaraki, 305–8573 Japan†† Dept of Computer Science, University of Victoria
Victoria, BC Canada
E-mail: †lichongjie@kde.cs.tsukuba.ac.jp, ††amagasa@cs.tsukuba.ac.jp, †††kitagawa@cs.tskuba.com,††††gsrivast@uvic.ca
Abstract Privacy concerns in publishing graph data, such as social-network graphs, have been gaining much public attentions in recent years due to the growing demands for publishing graph data containing privacy. So far, there
have been lots of researches focusing on a labeled graph anonymization problem that is more applicable and sincemore diﬃcult than that in unlabeled situations. In this paper we address the K-anonymity problem in edge-labeledgraphs based on the label-bag model. We provide eﬃcient greedy algorithms and evaluate them by experiments on
both synthetic and real data. Further we extend the algorithm considering other utility measurements and showthat our algorithm can be applied to varied utility metrics.
Key words Graph Privacy, K-anonymity, Label-bag, Utility

1. Introduction

edges that describe the attributes of entities or properties asshown in Figure 1.

Social networks (SNs) have shown remarkable development
in recent years. Due to the rapid proliferation of SNs, there
is a growing concern in privacy. SN data publishing is oneof the main channels for privacy breaches. SN data owners,
such as Facebook and LinkedIN, sometimes have responsibility to publish their data for various purposes. In this case,transforming data in such a way that privacy information is

Figure 1 Social Network Graph

not released is important. Such data transformation is called”anonymization”.

By having access to this graph, adversaries, with their ex-

In many cases, SN data is represented as a graph G =isting knowledge about some involved entities (i.e. Bob has(V, E), where vertices (V ) represent entities and edges (E)3 friends), can gain more information such like that node

represent relationship between them. To model more com-

3 is representing Bob and he is an instructor (since node 3

plex information, a graph may have labels on vertices and/or

is the only node with degree 3 in this graph). To preventthe privacy of the entities from being violated, an appropri-[11] further discussed the K-isomorphism situation with con-ate graph anonymization method is needed to sanitize thesideration on link information. Recent years, attentions wereoriginal graph before publishing.

paid on edge-labeled problems like Yuan [7] and Kapron [4].

Varied anonymization methods have been proposed to re-

In terms of the anonymization methods used, there are pro-trieve the privacy requirement and to realize it with min-posals focusing on edge addition/deletion [3] [4] [6] [11] [18],imum extra information added becomes a challenging task.

vertex/edge addition [12] [16], vertex generalization [14], edge

The concept utility is then proposed to measure the informa-label generalization [7] and class/cluster-based method [1]tion loss during data publishing. Therefore most researches[13]. In terms of the attack model, there are models focusing

aim to solve the anonymity problem with the least informa-on entity re-identiﬁcation like [2] [3] [12], link re-identiﬁcation

tion loss, or the largest utility, within extent privacy level.

like [8] [20], or many others considering both sides such as [7]In this paper we address the K-anonymity problem of edgelabeled graphs based on the label-bag model. Since it has[11]. Other approaches may be related to active attacks likeBackstrom [5], in which attackers may change the data.

been shown that the problem is NP-hard [4], we provide

Our work is inspired mainly by [4] [7]. However, we focus

heuristic methods based on edge-addition in which we try

on edge addition operation instead of label generation meth-

to include the utility measurement as well. Additionally, we

ods in [7] that is essentially a direct extension from unlabeledevaluate the eﬀectiveness of our proposed scheme in somemodels. The core idea of [7] is to realize K-degree anonymity

experiments.

and generalize edge labels, which introducing a lot of noises

The rest of this paper is organized as follows. Section 2 introduces some related works and we formalize the problem in(noticing that in the early grouping and addition steps, edge
labels are not taken into consideration).

Section 3. Section 4 gives the proposed methods and some

In some cases we may have restrictions not to modify the

discussion of utility measurement is involved in Section 5.

edge labels. Kapron [4] gives deﬁned label sequences instead

We show the results and analysis of experiments in Sectionof degree sequences and proved that ﬁnding a result for the

6 and make a conclusion in Section 7.

label sequence based anonymization problem with minimum

2. Related Work

cost is N P -hard when K > 2. What is more, this result
can be used to prove the N P -hardness of some previously

Privacy-preserving graph publishing is to transform adeﬁned anonymization problems in unlabeled situations: K-graph into another in such a way that adversaries with cer-neighborhood [6], i-hop anonymity [13] and k-symmetry [12].

tain background knowledge cannot get the identity and can-It can be easily understood that an applicable algorithm

not re-identify the entities and/or relations. So far, there

for the label-graph anonymization problem can be applied

have been lots of methods proposed to address the graphto unlabeled graph situations with very slight modiﬁcation.

anonymization problem.

However in [4] only the algorithm for bipartite graph withThis problem can be categorized into several classes ac-

K = 2 is given, which belongs to P . For this reason, in thiscording to the graph model and quantity of knowledge that

paper, we provide greedy algorithms based on label-graphs.

adversaries are assumed to have. The main part of researches

Formal deﬁnition of the problem is given in the next section.

are focusing on anonymizing structural information. Thesemethods can be roughly divided to two categories: unla-

3. Problem Deﬁnition

beled graph anonymization [2] [3] [6] [10] [11] [12] [13] and la-

Now we formally deﬁnition the label-bag based graph

beled graph anonymization [4] [7]. Labeled cases can be fur-anonymization problem. The deﬁnition of label-bag (LB)

ther divided according whether vertices or edges (or both)is as follows:

are labeled. Most early works focus on unlabeled or vertexlabeled cases. Sweeney [2] gave the early idea of K-anonymity
by replacing the identiﬁers of published data. Liu [3] deﬁned
the K-degree anonymity. This work was assuming that only
the degrees of certain vertices are known by the adversary.
Zhou [6] considered neighborhood attacks of a certain ver-Deﬁnition 1. label-bag (LB): A label-bag is a multi-setof labels. For a vertex vi , LBi is the set of all labels on edges
which have one end point of vi .
With the deﬁnition of a label-bag, we can deﬁne the concept of label-bag based K-anonymity.

tex and is extended by Tripathy [13], who assumed the adversaries having more information beyond 1-neighborhood
knowledge. Later researches such like K-automorphism [10]and K-symmetry [12] proposed models with stronger privacy
assurance on the whole structure property of graphs. Cheng

Deﬁnition 2. label-bag based K-anonymity (LB Kanonymity): Given an simple edge-labeled graph G and integer K, for any vertex v in graph G, there exists at least K-1
vertices with the same label-bag.

Figure 2 Example of LB K-anonymity

In the deﬁnition, a simple graph means an undirected
graph without self-loop or multi-edges. For example, Figure 2(b) is an anonymized version of the original graph in
Figure 2(a) by replacing identiﬁes (names) with meaninglessFigure 3 Algorithm Overview

arbitrary unique numbers. The label-bag of vertex 2 and 3
in Figure 2(b) is {a,b} and {a,b,b} respectively (In the following of the paper, we may use strings like ’ab’ and ’abb’
to represent the label-bag just for simplicity ).

is allowed in this problem setting. In other words, we do notconsider other operations, such as edge deletion or perturbation.

Then we are able deﬁne the label-bag based anonymization
problem. As have been mentioned, besides privacy requirements, another necessary task of privacy-preserving data
publishing is to assure the usefulness of resulted anonymized
data. There is a need to include the measure of information
loss to the process of solving such kind of problems.

4. LB K-anonymity
As already mentioned above, the LB K-anonymity problem
is NP-hard. So we propose a two-phase heuristic algorithm.
Figure 3 shows the overview of our method. First we divide the input vertex sets into several groups and check if

Deﬁnition 3. LB K-anonymity problem: Given an
simple edge-labeled graph G = (V, E) and an integer K(K >=the LB K-anonymity condition is satisﬁed. If so, the result2), the LB K-anonymity problem is to construct a graphaddition phase. The second phase is iterated until the LB00would be output. Otherwise, we move to the second edge-

G = (V, E ∪ ∆E) such that G satisﬁes LB K-anonymity

K-anonymity condition is satisﬁed. Here a new term called

condition with the minimum information loss.

TLB is used to record the graph state, which will be explaned
later. Details of each phase will be introduced in sections 4.1

Deﬁnition 4. LB K-anonymity problem 2: Given an
simple edge-labeled graph G = (V, E) and an integer K(K >=and 4.2 respectively. Now we give some deﬁnitions used in
the algorithm introduction.

2), the LB K-anonymity problem 2 is to construct a graph
G0 = (V, E ∪ ∆E) such that G0 satisﬁes LB K-anonymity
condition and makes |∆E| minimal.

Deﬁnition 5. target label-bag (TLB): For each group
gm , T LBm is the ideal LB that all members in this groupare supposed to reach.

The above deﬁnition is modiﬁed from that of [4]. Here
we use the term ”label-bag”, since we do not consider theDeﬁnition 6. residual label-bag (RLB): For every ver-order among labels, whereas ”label sequence” is used in [4].

tex vi , RLBi is the diﬀerence between T LBm and LBi , where

It is easily to ﬁnd that Deﬁnition 4 is just an extension ofvi belongs to group gm .

Deﬁnition 3 by specify the measurement as ”make |∆E| minimal”. Making the number of added edges minimum is nota restricted condition in all LB K-anonymity problems. For
example, the sum of degree diﬀerence of all vertices is also a

Deﬁnitions 4 and 5 deﬁne two diﬀerent kinds of label-bags,
one for an anonymous group while the other for a vertex.
The following equation shows how to compute the T LBm
for group m.

possible criteria even with the same edge addition/deletion
setting, although it is essentially equivalent to the numberof added/deleted edges (see [3] for more details). In the rest
paper, we assume Deﬁnition 4 as our main topic.
Figure 2(c) shows how to make a graph LB K-anonymized
by adding edges to graph G in Figure 2(b). G0 satisﬁes LB
K-anonymity for any K <= 4. Note that only edge addition

T LBm =

X

LBi

(1)

i∈gm

Here an operation ” + ” combines two label-bags and gives
the union of two multi-sets. For example, ’aa’+’ab’=’aab’
and ’aab’+’bb’=’aabb’. In other words,if a 3-size group contains vertices with label-bag ’aa’,’ab’ and ’bb’, we can tellthe TLB for this group is ’aabb’.
The equation below shows the way to calculate RLB. Also
this is the relationship between TLB and RLB.
RLBi = T LBm − LBi(2)

Here the operation ” − ” means to compute the label-bag
that belongs to LBi but not LBj .
4. 1 Grouping
The ﬁrst phase is to divide the vertices into several nonoverlapping subsets called anonymous groups. We utilize the
Figure 4 Algorithm Overview

TLB as a measurement to result in good grouping. Two different algorithms are used.
First is the feature based grouping algorihtm. This algorithm repreats a sequential scan to all vertices. Within each
step, the vertex with least TLB increse is chosen to be added
to group g until it reaches the pre-deﬁned group size. Algo-

A prototype-base hierarchical clustering method is used.
The group set is initialized with vertex set V and we keep
merging the closet clusters. Distance between two cluster isdeﬁned as:rithm 1 shows the pseudo code of feature based grouping.

Dist1 :

Dist(gmi , ggj ) = |T LBmi − T LBmj |+|T LBmj − T LBmi |(3)

Algorithm 1 Feature based Grouping
Input: Graph G = (V, E), strategy s

A major drawback of this clustering grouping method is

Output: Grouping {g}that group size is not taken into consideration when choos-

1: {g} ← empty;

ing closet clusters, while in fact it could be much easier to

2: for m = 1 to s.numOf group(m) do
3:

T LBm ← ∅4:

for i = 1 to |gm | do

5:ﬁnd v in V with least |T LBm |6:

insert v to group gm

7:

T LBm = ComputeT LB(T LBm , LBi )8:

end forsatisfy the same T LB for a group with smaller size than alarger one. So, we give two alternative distance metrics asfollows:
Dist2 :

Dist(gmi , gmj ) = Dist1 ∗ (|gmi | + |gmj |)Dist3 :

Dist(gmi , gmj ) = (T LBmi − T LBmj ) ∗ |gmj |9: end for(4)+(T LBmj − T LBmi ) ∗ |gmi |(5)Since the edge addition procedure highly depends on the

The function in last line would be responsible for the sit-

previous stage and the property of a grouping strategy would

uation when only one cluster is under size K while it cannot

have great inﬂuence to the ﬁnal cost, a more eﬀective group-

be merged to any other one according to condition C. In that

ing algorithm is need. Inspired by clustering approaches like

case, we can merge this cluster with a previous cluster which

Campan [9], we give a clustering based method shown in Al-

would results in minimum increase to the original value ofgorithm 2.

|T LB|.
4. 2 Edge Addition

Algorithm 2 Clustering based Grouping
Input: Graph G = (V, E), integer K

After we have assigned vertices to groups, before we start

Output: Grouping {g}to add edges to make all groups satisfying the anonymity

1: {g} ← V ;condition, value of TLB for each group and RLB for each

2: while !(∀|gm | >= K or no more merging) do
Merging two closet clusters with condition C;
3:

vertex need to be calculated for later use. Figure 5 is an

4: end while

through feature based grouping algorithm.

5: {g} ← GroupAdjust({g})

example showing grouping result of graph in Figure 4(a),As described in Figure 3, two steps are performed toachieve ﬁnal LB K-anonymity state. Firstly we check all

Here condition C refers to: Any clusters with size larger

unconnected pairs of vertices with a common label in theirthan K are not further merged. Considering that traditional

RLB. We can ﬁnd that both vertices 7 and 9 in Figure 5

clustering methods have no restrictions on cluster sizes, thishave a label 0 b0 . So, an edge can be added in between (Fig-condition can eﬀectively help to reduce the average cluster

ure 4(b)). However, it is impossible to add an edge of label(group) size and avoid bias clustering result.

0 0

a to vertices 4 and 8 since there already exists one andproperties as introduced in [14]: degree, path length, transitivity and so on. The other kind is related to the answers toextent queries like [7] and [20].
The utility metrics used in our paper are belonging to theﬁrst category as follows:(1) Degree Distribution and Label Distribution. They are
the measurement of degree and label property of graph data.
EMD value (Earth Mover’s Distance) [19] is used to measure the diﬀerence between two distributions. We adapt thisFigure 5 Algorithm Overview

concept to our research to calculate EMDD (EMD for degree) and EMDL (EMD for label). According to [19], having

we cannot ﬁnd any other pairs. In this situation, procedure
T LBAdjustment() is conducted as shown in Figure 4(c), we
0 0increase the TLB of group 1 by a and succeed to ﬁnd vertex

two signature (distributions) P = {(p1 , wp1 ), ..., (pm , wpm )},Q = {(q1 , wq1 ), ..., (qn , wqn )}, Earth Mover’s Distance is deﬁned as
EM D(P, Q) =pair 8 and 9. We follow this route until all nodes satisfy the

Pm Pn

i=1
j=1
P
m Pn

j=1 fij

i=1

condition that T LB = LB.

dij fij(6)

where dij and fij represent the distance an ﬂow between

Although it seems impossible to expect number of pairs

cluster pi and pj . This model is applied to network graph sce-being found in the next iteration of GreedyEdgeAddition(),nario by [17] in the following way. Let the attribute domainsame characteristics can help to ﬁnd a better candidate groupof numerical values be {v1 , v2 , ..., vm } and ri = pi − qi , (i =for T LBAdjustment(), like group 1 in the previous case. The

1, 2, ..., m), the EMD value can be calculated asfollowing few factors are thought to be meaningful when selecting a candidate group:(1) average degree of the group;(2)EM D(P, Q) =average |RLB| value;(3) connectivity to those vertices withlarge |RLB| and (4) connectivity with other group members.
The ﬁrst factor is straightforward since vertex with larger degree can be more diﬃcult to be wired with others. However
most real-data of social network is so sparse that make theinﬂuence of this factor relatively slight. The last two factors mean the possibility vertices of the candidate group can
be wired to other vertices. They are quite eﬀective but isexpensive to calculate. In all, a strategy combining factors(2)(3)(4) is used in our algorithm: sort all groups in descending order of their values of total |RLB| values while excluding
those with low connectivity.
By carefully choosing the candidate group, the algorithm
can terminate in ﬁnite time (unless the situation of no answer and need to be solved by other means like adding noise
nodes, which is beyond the range of this paper).

5. Improved Algorithm on Utility
Method introduced above focus on edge-labeled K-

1(|r1 |+|r1 +r2 |+...+|r1 +r2 +...+rm−1 |)m−1(7)

In our case, to calculate EMDD, let Distribution P ={(d1 , p1 ), (d2 , p2 ), .., (dt , pt )}, Q = {(d1 , q1 ), (d2 , q2 ), ..., (dn , qn )},having their degree sequences sorting in ascending order.
Here pi (i = 1, , 2...t) and qj (j = 1, 2, ..., n) means the weightof each degree di and dj respectively. Let m = maxt, n, thecommon degree domain can be expressed as {d1 , d2 , ..., dm }while formula 5.2 can be used directly.
Similarly, in case of EMDL, let {l1 , l2 , ...lm } be the label
domain makes formula 5.2 applicable.
(2) Shortest Path Distance (SPD). This is a widely usedmeasurement in graph theory which means sum of weights ofshortest path between two vertices. We utilize the average
shortest path distance (ASPD) and calculate it through thefamous Floyd-Warshall algorithm [22].
The Floyd-Warshall algorithms compares all pair of vertices’ paths in a graph with complexity of O(N 3 ). The ideaof this algorithm can be expressed by the following recursive
equation.

anonymity problem under the goal of less number of edges

SP D(i, j, k) = min(SP D(i, j, k − 1), SP D(i, k, k − 1)added. Nevertheless, in order to retain varied characteristics+SP D(j, k, k − 1))(8)of the original graph, other utility measurement should be
included. So in this chapter we introduce some other utility

By computing this for all (vi , vj ) pairs and for k =metrics an how their can be applied to our LB K-anonymity

1, 2, ..., |V |, we are able to get average shortest path distancemodel.

byIn terms of the social network data, some of the graphproperties are of interest. Most of them are basic graph

ASP D =X
1
SP D(vi , vj )|(vi , vj )|vi ∈ V, vj ∈ V | v ∈V,v ∈V
i

j

(9)

(3) Clustering Coeﬃcient (CC). This is a measure of how
vertices in a graph tend to cluster together. Again we use
the average local clustering coeﬃcient (ACC) a s criterion.
Clustering coeﬃcient can be roughly dived into two categories, global clustering coeﬃcient and local clustering coeﬃcient. Though they diﬀer in deﬁnition, core idea is tomeasure the ratio of k|edges|/|vertices|. Suppose for a vertex vi , its neighborhood Ni is deﬁned as {vj |e(vi , vj ) ∈ E},
then ENi = {e(vj , vk )|vj ∈ Ni , vk ∈ Ni } represents all the

Figure 6 Result on variation of K

edges between vertex i’s neighbors. The local clustering forvertex vi is deﬁned as follows.
CCi =|ENi ||Ni |(|Ni | − 1)

(10)

We can directly derive the formula for average clustering
coeﬃcient as
ACC =

1 X
CCi
|V | i∈V(11)

Applying these utility measurements to anonymization algorithms is very simple, the only diﬀerence is in the edge

Figure 7 Result on variation of L

addition step. Note that in the original method (without
utility consideration) introduced in Section 4, we decide a

could be either metric be introduced above.

match whenever two vertices share a common label in RLB

The new method considering utility metrics will bring ex-

and has no conﬂict of edge addition. While in new algorithm

tra execution expense, especially for case of ACC (O(N 2 )we tend to choose the candidate match with highest utility.

complexity) and ASPD (O(N 3 ) complexity). We evaluate

To achieve this we compute the utility score for every pair ofresulted utility scores of this method in the next section.

match before decision.

6. Experiments
Algorithm 3 Edge Addition Algorithm with Utility
Input: Graph G = (V, E), integer K, Grouping {g}, Utility Met-

We conduct a series of experiments to evaluate the eﬃciency and eﬀectiveness of our algorithm. Experiments are

ric C
Output: LB K-anonymity Graph G0 = (V 0 , E 0 )conducted in environment as Table 1.

1: {T LBm } ← GetT LB({gm })表 1 Experimental Environment

2: Q ← {v|cRLBi (l) > 0}
3: sort Q in descending order of cRLBi (l)CPU

2.26 GHz Intel Core 2 Duo

4: for each u ∈ Q do

Memory4GB 1067MHz DDR3

5:

minCost = IN F IN IT Y

6:

vv ← N U LL

7:for each v ∈ Q, v 6= u do8:

if !e(u, v) && (RLBu ∪ RLBv 6= ∅) then

Language/Compiler c/gcc-4.2

Since social network is well-modeled by the small world9:

cost = Compute(C, u, v)

graph, we use the Small World Graph generated by [23] as

10:

if cost < minCost thenthe synthetic data. Figure 6 and Figure 7 are the results on

11:

cost = minCost

12:

vv ← v

13:

end ifvariant of anonymity level parameter K and number of labels L in 500 size synthetic dataset. Both of these parameters
are positive correlated to the total cost. In case of parame-

14:

end if15:

end forter K (ﬁxing L as 3), clustering based method, especially the16:

if minCost 6= IN F IN IT Y then

one with distance metric 3 has good result in relative small

add edge between u and vv

K values. While feature based algorithm performs best in

17:

end iflarger K situations. In terms of labels (K = 5), similarly

19: end forthe feature based algorithm and clustering based algorithm

18:

3 outperform the others.
Algorithm 6 is the description of GreedyEdgeAddition()

Table 2 shows the result of dataset-1, extracting fromfunction considering utility metrics. The utility metric C

Speed Dating Data [24]. The graph is constructed by 551

表 4 Real Dataset-1 using utility metric

Statics of Output Anonymized Graph
Applied Utility COST EMDD EMDL

ACC

ASPD

original

169

0.01980.00740.0455 3.2840

EMDD

169

0.01980.00740.0431 3.2954

EMDL

169

0.01980.00740.0431 3.2954

ACC

169

0.01980.00740.0051 2.5269

ASPD

169

0.01980.00740.0192 2.7787

In the result of real dataset-1, although EMD based meth-

Figure 8 Execution Timeods do not have any improvement, which probably due tovertices, 8368 edges and 2 kinds of labels. The max degreeof this graph is 22 and the average degree is around 15. The
result is close to that of synthetic data and again reﬂects
that clustering based algorithm with distance metric 3 andfeature based grouping algorithm ﬁt for diﬀerent K values.

sult in good utility compared to the baseline.
For the sake of great computation cost, only EMDD and
EMDL based metrics are evaluated for the second datasets.
In this case both of these two utility metrics have no manifest inﬂuence to the results. This is because the low average
degree of the whole graph makes the result of a few rewiring

表 2 Real Dataset-1

K

small label size of data, methods using ASPD and ACC re-

Feature based Clustering 1 Clustering 2 Clustering 3

5

169

112

117

131

10

398

309

312

291

20

664

567

526

540

50

1259

1325

2239

1820

not obvious.
表 5 Real Dataset-2 using utility metric

Statics of Output Anonymized Graph
Applied Utility Metrics COST EMDD

In result of Table 3 we use a dataset extracted from theco-author network on condensed matter section of arXiv E-

EMDL

original

1730

0.00180.0060EMDD

1733

0.00180.0060EMDL

1733

0.00180.0060

print Archive [25]. The graph consists of 16726 vertices and47594 edges with the number of labels set as 3. Average andmax degree are 5.09 and 107 respectively. It can be seenthat feature based algorithms outperforms the others since
K exceeds 10.

In this paper, we discussed the K-anonymity problem inprivacy-preserving data publishing.

This is an extension

from the unlabeled model and can be applied to many real-

表 3 Real Dataset-2

K

7. Conclusion

Feature based Clustering 1 Clustering 2 Clustering 3

5

1730

1871

1740

1628

10

3212

3779

3317

3063

20

5207

6864

6053

5706

50

10337

16502

12450

11629

world situations. We provide a heuristic algorithm based onlabel-bag model and realize it in two diﬀerent ways.
We evaluate them by some experiments on both synthetic
and real data. Through the results, it is proved to be eﬃcient and of good utility. Also, we investigate how choices
in parameters would inﬂuent the cost. In consideration of

Figure 8 shows the exectuion time of 2 phases for each al-

the problem when there does not exist an answer, we give

gorithms applied to real dataset-1. Since the edge additionan algorithm based on noise vertex. An improved method istime is relatively small to that of grouping, to choose theproposed considering four utility metrics and is proved to befeature based algorithm is more eﬃcient.

of good utility through experiment results.

Table 4 and 5 compare the results of methods considering

There is still a need to improve the edge addition algo-utility with previous one on the 3 real datasets. Row withrithm to guarantee the realization of LB k-anonymity graphlabel ”original” is the baseline that contains all utility scoresin arbitrary condition. To extend our model to utilize edgeof resulted LB K-anonymity graph by using method without

deletion and label generalization operations are other inter-

considering utility metrics. Following are several lines eachesting topics.

representing the results by applying diﬀerent utility measure-Acknowledgement

ments.
This work has been supported in part by Grant-in-Aid forYoung Researchers (B) (23700102)

文

献[1] S. Bhagat, G. Cormode, B. Krishnamurthy, D. Srivastava.
Class-based graph anonymization for social network data.
VLDB Endowment 2009.
[2] L. Sweeney. k-anonymity: a model for protecting privacy. International Journal on Uncertainty anonymization
on graphs, SIGMOD 2008.
[3] K. Liu, E. Terzi. Towards identity anonymization on graphs.
SIGMOD 2008.
[4] B. Kapron, G. Srivastava, S. Venkatesh. Social network
anonymization via edge addition. ASONAM 2011.
[5] L. Backstrom, C. Dwork, J. Kleinberg. Wherefore art thour3579x?: anonymized social networks, hidden patterns, andstructural steganography. IW3C2 2007.
[6] B. Zhou, J. Pei. Preserving privacy in social networks
against neighborhood attacks. ICDE 2008.
[7] M. Yuan, L. Chen, Philip S. Yu. Personalized privacy protection in social networks. VLDB Endowment 2010.
[8] C. Tai, Philip S. Yu, D. Yang, M. Chen.
Privacypreserving social network publication against friendship attacks. SIGKDD 2011.
[9] A. Campan, T. Marius Truta. A clustering approach fordata and structural anonymity in social networks. PinKDD
2008.
[10] L. Zou, L. Chen, M. Tamer Özsu. K-automorphism: a general framework for privacy preserving network publication.
VLDB Endowment 2009.
[11] J. Cheng, AW Fu, J. Liu. K-isomorphism: privacy preserving network publication against structural attacks. SIGMOD 2010.
[12] W. Wu, Y. Xiao, W. Wang, Z. He, Z. Wang. K-symmetry
model for identity anonymization in social networks. EDBT2010.
[13] B. Thompson, D. Yao. The union-split algorithm andcluster-based anonymization of social networks. ASIACCS
2011.
[14] M. Hay, G. Miklau, D. Jensen, D. Towsley, P. Weis. Resisting structural re-identiﬁcation in anonymized social networks. VLDB Endowment 2008.
[15] X. Liu, Y. Song, S. Bressan. Fast identity anonymization
on graphs. DEXA 2012.
[16] S. Chester, B. Kapron, G. Ramesh, G. Srivastava, A.
Thome. K-anonymization of social networks by vertex addition. ADBIS 2011.
[17] N. Li, T. Li. t-closeness: Privacy beyond k-anonymity andl-diversity. ICDE 2007.
[18] BK Tripathy, GK Panda. A new approach to manage
security against neighborhood attacks in social networks.
ASONAM 2011.
[19] Y. Rubner, C. Tomasi, L.J. Guibas. The earth mover’s distance as a metric for image retrieval. Int. J Comput 2000.
[20] A. Korolova, R. Motwani, U.N. Shubha, Y. Xu. Link privacy in social networks. ICDE 2008.
[21] http://math.standford.edu/muellner.
[22] Cormen, H. Thomas, Leiseron, E. Charles, Rivest, L.
Ronald Introduction to Algorithms 1990.
[23] Networkx 1.6. http://networkx.lanl.gov/index.html.
[24] Speed Dating Data. http://ﬂowingdata.com[25] M. Newman. Scientiﬁc collaboration networks 2. Shortest
paths, weighted networks, and centrality 2001.