what-when-how
In Depth Tutorials and Information
knowledge can lead to different types of privacy attacks. Reference [1] just
focuses on the background knowledge about the immediate neighbors of the
target vertex.
Given a vertex
u V G
∈
( )
,
u
is
k
-anonymous in anonymization
G
'
if there
are at least (
k
- 1) other vertices, denoted as
v
−
∈
,...
v
V G
(
)
, such that the
1
k
1
neighborhoods
Neighbor A u Neighbor A v
(
( )),
(
(
)),...,
Neig
hbor A v
G
'
(
(
))
−
1
are isomorphic. hus,
G
'
is
k
-anonymous if any vertex in
G
is
k
-anonymous
in
G
'
.
G
'
G
'
1
k
3. Usage of anonymized social networks: Different applications should adopt
various anonymization schemes. In Reference [1], the anonymization scheme
applied is based on aggregate network queries that are popularly used in many
network applications whenever aggregated data needs to be queried.
4. Problem complexity: he complexity of
k
-anonymity problem defined in
Reference [1] is NP-hard.
Reference [1] also proposes an effective anonymization method, which consists of
two steps:
10.2.1 Neighborhood Extraction and Coding
According to the requirements of
k
-anonymity, the vertices should be divided
into groups and their neighborhoods need to be anonymized. As a graph iso-
morphism problem, Reference 1 introduces neighborhood component coding
technique to tackle the isomorphism NP-hard problem [3]. As a result, isomor-
phism can be determined by the corresponding codes. A neighborhood com-
ponent
C
is defined as a maximal connected subgraph in
Neighbor u
G
( )
. As
shown in Figure 10.3, there are three neighborhood components, C
1
, C
2
, C
3
, in
Neighbor u
G
( )
.
hus, in order to encode the whole neighborhood, the components should be
coded first. Reference 1 suggests the use of
DFS-tree
(
depth-irstsearchtree
) [4] to
encode the vertices in the preorder of
T
. As shown in Figure 10.4a,b,c, (b) and (c)
are two different DFS-trees of graph
G
in (a).
he forward edges
included in the
DFS-trees and
thebackwardedges
excluded from the DFS-trees are illustrated as
the thick edges and the thin edges, respectively, in Figure 10.4b,c. hen the vertices
are encoded form
v
0
to
v
3
based on the preorder of the corresponding DFS-trees.
hus, the DFS-tree for a graph
G
is not unique. To tackle this problem, Reference
1 uses a
minimumDFS
code notation proposed in Reference 5.
To identify the
minimumDFScode
, it is necessary to give the definition of a lin-
ear order
≺
on edges. For edges
e
=
(
=
v v
,
)
and
e
'
(
v v
,
)
(in any edge
(
v v
,
),
i
j
i
'
j
'
i
j
≺
'
if (a) when both
e
and
e
'
are forward edges,
j
<
'
or
(
i
<
),
e
i
> ∧ =
i
'
j
j
');
<
'
or
(
= ∧ <
(b) when both
e
and
e
'
are backward edges,
i
i
i
'
j
j
')
; (c) when
e
is a
forward edge and
e
'
is a backward edge,
j
ʺ
'
; or (d) when
e
is a backward edge
<
'
.
and
e
'
is a forward edge,
i
