374
CHAPTER 10. MINING SOCIAL-NETWORK GRAPHS
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 meth-
ods”) to formulate the problem of partitioning a graph to minimize the number
of edges that connect diﬀerent 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 diﬀerent 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 example 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 consists only of the edge (B, D) and is of size 1. No
nontrivial cut can be smaller.
A
B
D
E
G
F
C
H
Smallest
Best cut
cut
Figure 10.11: The smallest cut might not be the best cut
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
