what-when-how
In Depth Tutorials and Information
Label Hierarchy
*
New Neighbor Nodes
l
7
l
6
w
1,
l
4
w
2,
l
5
l
4
l
6
l
1
l
2
l
3
Neighbor
G
(
u
)
u
1,
l
2
u
5,
l
1
u6, l2
u
7,
l
1
u
8,
l
3
u
3,
l
1
u
4,
l
4
u
2,
l
4
C
2(
u
)
C
3(
u
)
C
1(
u
)
Neighbor
G
(
v
)
v
1,
l
2
v
4,
l
2
v
6,
l
1
v
6,
l
5
v
7,
l
1
v
8,
l
2
v
3,
l
1
v
2,
l
5
C
2(
v
)
C
3(
v
)
C
1(
v
)
Anonymized Neighborhood
s
1,
l
2
s
3,
l
1
s
4,
l
4
s
4,
l
2
s
6,
l
1
s
6,
l
5
s
7,
l
1
s
8,
l
3
s
2,
l
4
C
1(
s
)
C
2(
s
)
C
3(
s
)
Figure 10.5
Anonymizing two neighborhoods. (From Bin Zhou and Jian Pei.
DataEngineering,2008.
IEEE 24th International Conference on ICDE 2008
.April
7-12,2008,pp.506-515.)
no vertex in
C
1
(
v
) matching with
u
4
in
C
1
(
u
). In such a case, we should find a vertex
w V G
1
∈
( )
which is not included in
C
1
(
u
) or
C
1
(
v
) , and add
w
1
to
C
1
(
v
). As a result,
C
1
(
u
) and
C
1
(
v
) can be anonymized to the same structure. he process of selection
of
w
1
is introduced as below.
First, select such a vertex in
V
(
G
) that is unanonymized and with the smallest
degree. If there is more than one vertex that satisfy the requirements, we can choose
the one with the closest label according to the normalized certainty penalty. If there
is no unanonymized vertex, we then select an anonymized vertex
w
satisfying the
requirements of the degree and the label, and categorize
w
and other (
k
- 1) vertices
in its same group as unanonymized.
