Database Reference
In-Depth Information
10.4.2
Normalized Cuts
A proper definition of a “good” cut must balance the size of the cut itself against the differ-
ence in the sizes of the sets that the cut creates. One choice that serves well is the “normal-
ized cut.” First, define the
volume
of a set
S
of nodes, denoted
Vol
(
S
), to be the number of
edges with at least one end in
S
.
Suppose we partition the nodes of a graph into two disjoint sets
S
and
T
. Let
Cut
(
S, T
) be
the number of edges that connect a node in
S
to a node in
T
. Then the
normalized cut
value
for
S
and
T
is
EXAMPLE
10.15 Again consider the graph of
Fig. 10.11
.
If we choose
S
= {
H
} and
T
= {
A,
B, C, D, E, F, G
}, then
Cut
(
S, T
) = 1.
Vol
(
S
) = 1, because there is only one edge connected
to
H
. On the other hand,
Vol
(
T
) = 11, because all the edges have at least one end at a node
of
T
. Thus, the normalized cut for this partition is 1/1 + 1/11 = 1
.
09.
Now, consider the preferred cut for this graph consisting of the edges (
B, D
) and (
C, G
).
Then
S
= {
A, B, C, H
} and
T
= {
D, E, F, G
}.
Cut
(
S, T
) = 2,
Vol
(
S
) = 6, and
Vol
(
T
) = 7.
The normalized cut for this partition is thus only 2/6 + 2/7 = 0
.
62.
□
10.4.3
Some Matrices That Describe Graphs
To develop the theory of how matrix algebra can help us find good graph partitions, we
first need to learn about three different matrices that describe aspects of a graph. The first
should be familiar: the
adjacency matrix
that has a 1 in row
i
and column
j
if there is an
edge between nodes
i
and
j
, and 0 otherwise.
EXAMPLE
10.16 We repeat our running example graph in
Fig. 10.12
. Its adjacency matrix
appears in
Fig. 10.13
. Note that the rows and columns correspond to the nodes
A, B, . . . ,
G
in that order. For example, the edge (
B, D
) is reflected by the fact that the entry in row 2
and column 4 is 1 and so is the entry in row 4 and column 2.
□
Figure 10.12
Repeat of the graph of
Fig. 10.1
