378
CHAPTER 10. MINING SOCIAL-NETWORK GRAPHS
is orthogonal to 1, we must have
xT1 =
n
X
i=1
xi = 0
In addition for the Laplacian matrix, the expression xTLx has a useful equiv-
alent expression. Recall that L = D −A, where D and A are the degree and
adjacency matrices of the same graph. Thus, xTLx = xTDx −xTAx. Let us
evaluate the term with D and then the term for A. Here, Dx is the column vec-
tor [d1x1, d2x2, . . . , dnxn], where di is the degree of the ith node of the graph.
Thus, xTDx is Pn
i=1 dix2
i .
Now, turn to xTAx. The ith component of the column vector Ax is the sum
of xj over all j such that there is an edge (i, j) in the graph. Thus, −xTAx is the
sum of −2xixj over all pairs of nodes {i, j} such that there is an edge between
them. Note that the factor 2 appears because each set {i, j} corresponds to two
terms, −xixj and −xjxi.
We can group the terms of xTLx in a way that distributes the terms to each
pair {i, j}. From −xTAx, we already have the term −2xixj. From xTDx, we
distribute the term dix2
i to the di pairs that include node i. As a result, we
can associate with each pair {i, j} that has an edge between nodes i and j the
terms x2
i −2xixj +x2
j. This expression is equivalent to (xi −xj)2. Therefore, we
have proved that xTLx equals the sum over all graph edges (i, j) of (xi −xj)2.
Recall that the second-smallest eigenvalue is the minimum of this expression
under the constraint that Pn
i=1 x2
i = 1. Intuitively, we minimize it by making
xi and xj close whenever there is an edge between nodes i and j in the graph.
We might imagine that we could choose xi = 1/√n for all i and thus make this
sum 0. However, recall that we are constrained to choose x to be orthogonal to
1, which means the sum of the xi’s is 0. We are also forced to make Pn
i=1 x2
i be
1, so all components cannot be 0. As a consequence, x must have some positive
and some negative components.
We can obtain a partition of the graph by taking one set to be the nodes
i whose corresponding vector component xi is positive and the other set to
be those whose components are negative. This choice does not guarantee a
partition into sets of equal size, but the sizes are likely to be close. We believe
that the cut between the two sets will have a small number of edges because
(xi−xj)2 is likely to be smaller if both xi and xj have the same sign than if they
have diﬀerent signs. Thus, minimizing xTLx under the required constraints will
tend to give xi and xj the same sign if there is an edge (i, j).
Example 10.19 : Let us apply the above technique to the graph of Fig. 10.16.
The Laplacian matrix for this graph is shown in Fig. 10.17. By standard meth-
ods or math packages we can ﬁnd all the eigenvalues and eigenvectors of this
matrix. We shall simply tabulate them in Fig. 10.18, from lowest eigenvalue to
highest. Note that we have not scaled the eigenvectors to have length 1, but
could do so easily if we wished.
