10.9. SUMMARY OF CHAPTER 10
423
by the cut. Then add these two ratios to get the normalized cut value.
Normalized cuts with a low sum are good, in the sense that they tend to
divide the nodes into two roughly equal parts, and have a relatively small
size.
✦Adjacency Matrices: These matrices describe a graph. The entry in row
i and column j is 1 if there is an edge between nodes i and j, and 0
otherwise.
✦Degree Matrices: The degree matrix for a graph has d in the ith diagonal
entry if d is the degree of the ith node. Oﬀthe diagonal, all entries are 0.
✦Laplacian Matrices: The Laplacian matrix for a graph is its degree matrix
minus its adjacency matrix. That is, the entry in row i and column i of
the Laplacian matrix is the degree of the ith node of the graph, and the
entry in row i and column j, for i ̸= j, is −1 if there is an edge between
nodes i and j, and 0 otherwise.
✦Spectral Method for Partitioning Graphs: The lowest eigenvalue for any
Laplacian matrix is 0, and its corresponding eigenvector consists of all
1’s. The eigenvectors corresponding to small eigenvalues can be used to
guide a partition of the graph into two parts of similar size with a small
cut value. For one example, putting the nodes with a positive component
in the eigenvector with the second-smallest eigenvalue into one set and
those with a negative component into the other is usually good.
✦Overlapping Communities: Typically, individuals are members of several
communities. In graphs describing social networks, it is normal for the
probability that two individuals are friends to rise as the number of com-
munities of which both are members grows.
✦The Aﬃliation-Graph Model: An appropriate model for membership in
communities is to assume that for each community there is a probability
that because of this community two members become friends (have an
edge in the social network graph). Thus, the probability that two nodes
have an edge is 1 minus the product of the probabilities that none of
the communities of which both are members cause there to be an edge
between them. We then ﬁnd the assignment of nodes to communities and
the values of those probabilities that best describes the observed social
graph.
✦Maximum-Likelihood Estimation: An important modeling technique, use-
ful for modeling communities as well as many other things, is to compute,
as a function of all choices of parameter values that the model allows, the
probability that the observed data would be generated. The values that
yield the highest probability are assumed to be correct, and called the
maximum-likelihood estimate (MLE).
