what-when-how
In Depth Tutorials and Information
x
V2
x
V0
x
x
V1
x
V1
x
y
V0
y
z
V3
y
V2
z
V3
z
(a) Graph G
(b) DFS-tree T1
(c) DFS-tree T2
Figure10.4
DFScodes,startingfromdifferentvertices.(FromBinZhouandJian
Pei.DataEngineering,2008.
IEEE 24th International Conference on ICDE 2008
.
April7-12,2008,pp.506-515.)
( ) (
=
. hus, it is easy to compare the isomorphism and to calculate
the similarity between two neighborhoods where information loss is reduced dur-
ing anonymizing similar components.
NCC u NCC v
10.2.2 STNs Anonymization
Based on the predominant properties of STNs such as power law distribution of
node degree and small world theory, we can anonymize a network as well as pre-
serve the neighborhoods and properties of original networks.
k
vertices with same
degrees should be divided in a group according to the requirements of
k
-anonym-
ity. Besides, such a process should follow the descending order based on the power
law distribution.
10.2.2.1 Anonymization Quality Measure
Reference 1 proposes two methods to anonymize the neighborhoods of vertices:
generalizing vertex labels and adding edges, both of which result in some informa-
tion loss.
he information loss caused by generalizing vertex labels can be measured by
normalized certainty penalty [6]. Suppose label
l
1
of the vertex
u
is a leaf in the
label hierarchy and
l
≺
(
2
.
size
(*)
(* represents the most general category in the label hierarchy) is the total number of
leafs in the label hierarchy. he normalized certainty penalty of
l
2
is
l
. he number of leaves of
l
2
is denoted as
size l
2
1
size l
size
( )
(*)
=
2
NCP l
(
)
2
