10.4. PARTITIONING OF GRAPHS
375
partitions where one set is too small, then the best we can do is to use the
cut consisting of edges (B, D) and (C, G), which partitions the graph into two
equal-sized sets {A, B, C, H} and {D, E, F, G}.
✷
10.4.2
Normalized Cuts
A proper deﬁnition of a “good” cut must balance the size of the cut itself
against the diﬀerence in the sizes of the sets that the cut creates. One choice
that serves well is the “normalized cut.” First, deﬁne 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
Cut(S, T )
Vol(S)
+ Cut(S, T )
Vol(T )
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 ﬁnd good graph
partitions, we ﬁrst need to learn about three diﬀerent matrices that describe
aspects of a graph. The ﬁrst 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.
A
B
D
E
G
F
C
Figure 10.12: Repeat of the graph of Fig. 10.1
