Database Reference
In-Depth Information
10.4 Partitioning of Graphs
In this section, we examine another approach to organizing social-network graphs.
We use some important tools from matrix theory (“spectral methods”) to formulate the
problem of partitioning a graph to minimize the number of edges that connect different
components. The goal of minimizing the “cut” size needs to be understood carefully before
proceeding. For instance, if you just joined Facebook, you are not yet connected to any
friends. We do not want to partition the friends graph with you in one group and the rest
of the world in the other group, even though that would partition the graph without there
being any edges that connect members of the two groups. This cut is not desirable because
the two components are too unequal in size.
10.4.1
What Makes a Good Partition?
Given a graph, we would like to divide the nodes into two sets so that the
cut
, or set of
edges that connect nodes in different sets is minimized. However, we also want to constrain
the selection of the cut so that the two sets are approximately equal in size. The next ex-
ample illustrates the point.
EXAMPLE
10.14 Recall our running example of the graph in
Fig. 10.1
. There, it is evident
that the best partition puts {
A, B, C
} in one set and {
D, E, F, G
} in the other. The cut con-
sists only of the edge (
B, D
) and is of size 1. No nontrivial cut can be smaller.
In
Fig. 10.11
is a variant of our example, where we have added the node
H
and two extra
edges, (
H, C
) and (
C, G
). If all we wanted was to minimize the size of the cut, then the best
choice would be to put
H
in one set and all the other nodes in the other set. But it should
be apparent that if we reject 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
}.
□
Figure 10.11
The smallest cut might not be the best cut
