376
CHAPTER 10. MINING SOCIAL-NETWORK GRAPHS
Example 10.16 : We repeat our running example graph in Fig. 10.12. Its
adjacency matrix appears in Fig. 10.13. Note that the rows and columns cor-
respond to the nodes A, B, . . . , G in that order. For example, the edge (B, D)
is reﬂected by the fact that the entry in row 2 and column 4 is 1 and so is the
entry in row 4 and column 2.
✷


0
1
1
0
0
0
0
1
0
1
1
0
0
0
1
1
0
0
0
0
0
0
1
0
0
1
1
1
0
0
0
1
0
1
0
0
0
0
1
1
0
1
0
0
0
1
0
1
0


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 ith 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.
✷


2
0
0
0
0
0
0
0
3
0
0
0
0
0
0
0
2
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
2
0
0
0
0
0
0
0
3
0
0
0
0
0
0
0
2


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 diﬀerence between the
degree matrix and the adjacency matrix. That is, the Laplacian matrix L has
the same entries as D on the diagonal. Oﬀ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.
✷
