Database Reference
In-Depth Information
If we use both the second and third eigenvectors, we put nodes 2 and 3 in one group,
because their components are positive in both eigenvectors. Nodes 5 and 6 are in another
group, because their components are negative in the second eigenvector and positive in the
third. Node 1 is in a group by itself because it is positive in the second eigenvector and neg-
ative in the third, while node 4 is also in a group by itself because its component is negative
in both eigenvectors. This partition of a six-node graph into four groups is too fine a par-
tition to be meaningful. But at least the groups of size two each have an edge between the
nodes, so it is as good as we could ever get for a partition into groups of these sizes.
□
10.4.6
Exercises for Section 10.4
(a) The adjacency matrix.
(b) The degree matrix.
(c) The Laplacian matrix.
second-smallest eigenvalue and its eigenvector. What partition of the nodes does it suggest?
the third and subsequent smallest eigenvalues and their eigenvectors.
10.5 Finding Overlapping Communities
So far, we have concentrated on clustering a social graph to find communities. But com-
munities are in practice rarely disjoint. In this section, we explain a method for taking a
social graph and fitting a model to it that best explains how it could have been generated
by a mechanism that assumes the probability that two individuals are connected by an edge
(are “friends”) increases as they become members of more communities in common. An
important tool in this analysis is “maximum-likelihood estimation,” which we shall explain
before getting to the matter of finding overlapping communities.
