what-when-how
In Depth Tutorials and Information
he information loss caused by adding edges can be measured by the total num-
ber of edges added and the number of vertices induced from other neighborhood
for anonymization. Consider Neighbor u
G (
)
and Neighbor u
G (
)
are generalized to
1
2
Neighbor A u
G ' (
(
))
and Neighbor A u
G ' (
(
))
. Given
1
2
=
H Neighbor A u
(
(
))
Neighbor A u
(
(
))
G
1
G
2
and
H Neighbor A u
'
=
(
(
))
Neighbor A u
(
(
)),
G
'
1
G
'
2
he anonymization cost is
{
Cost u v
( , )
= ⋅
α
NCP v
( ')
+ ⋅
β
(
v v
,
) | (
v v
,
2
)
E H
(
),
1
2
1
v H
'
'
} + ⋅
(
)
γ
(
A v A v
(
),
(
))
E H
(
')
V H
(
')
V H
(
)
1
2
where α , β , and γ are the weights of three parts of cost predeined by users. he
first part is the normalized certainty penalty; the second part calculates the cost
of adding edges; the third part takes the number of vertices associated with the
anonymized neighborhood. We can balance these three parts by tuning the three
parameters. hus, the similarity between two neighborhoods is measured by the
anonymization cost.
10.2.2.2 Anonymizing Two Neighborhoods
First, we select all neighborhood components that totally match each other according
to the same minimum DFS code. For example, as shown in Figure 10.5, the neigh-
borhood component C u Neighbor u
G
3 ( ) ( exactly.
hen Reference 1 uses a greedy method to group these not completely
matched components based on the anonymization cost. Initially, we find two
vertices with the same degree and the same label in the two components. Select
the pair with the highest vertex degree when there are more than one pair of
such vertices.
If there is not such a pair of matching vertices, we relax the requirements of ver-
tex degree or label, compute the difference of degrees and the normalized certainty
penalty of generalizing the labels in the label hierarchy, and select the pair with the
minimum anonymization cost. hen, take a breadth-irst search to match vertices
one by one. hus, the similarity between the two components can be calculated by
the anonymization cost according to the matching process.
Regarding the components C 1 ( u ) and C 1 ( v ) in Figure 10.5, we select the pair of
vertices ( u 1 v 1 ) and take a breadth-first search ( u 2 v 2 and u 3 v 3 ). However, there is
matches C v Neighbor v
G
2 ( )
( )
Search WWH ::




Custom Search