Mining Social-Network Graphs - Mining of Massive Datasets - page 346

Figure 10.13 The adjacency matrix for Fig. 10.12

The second matrix we need is the degree matrix for a graph. This graph has nonzero
entries only on the diagonal. The entry for row and column i is the degree of the i th node.

EXAMPLE 10.17 The degree matrix for the graph of Fig. 10.12 is shown in Fig. 10.14 . We
use the same order of the nodes as in Example 10.16 . For instance, the entry in row 4 and
column 4 is 4 because node D has edges to four other nodes. The entry in row 4 and column
5 is 0, because that entry is not on the diagonal.

□

Figure 10.14 The degree matrix for Fig. 10.12

Suppose our graph has adjacency matrix A and degree matrix D . Our third matrix, called
the Laplacian matrix , is L = D − A , the difference between the degree matrix and the ad-
jacency matrix. That is, the Laplacian matrix L has the same entries as D on the diagonal.
Off the diagonal, at row i and column j , L has −1 if there is an edge between nodes i and j
and 0 if not.

EXAMPLE 10.18 The Laplacian matrix for the graph of Fig. 10.12 is shown in Fig. 10.15 .
Notice that each row and each column sums to zero, as must be the case for any Laplacian
matrix. □

Figure 10.15 The Laplacian matrix for Fig. 10.12

10.4.4 Eigenvalues of the Laplacian Matrix

We can get a good idea of the best way to partition a graph from the eigenvalues and eigen-
vectors of its Laplacian matrix. In Section 5.1.2 we observed how the principal eigenvector
(eigenvector associated with the largest eigenvalue) of the transition matrix of the Web told
us something useful about the importance of Web pages. In fact, in simple cases (no tax-