10.5. FINDING OVERLAPPING COMMUNITIES
381
! Exercise 10.4.2: For the Laplacian matrix constructed in Exercise 10.4.1(c),
ﬁnd the second-smallest eigenvalue and its eigenvector. What partition of the
nodes does it suggest?
!! Exercise 10.4.3: For the Laplacian matrix constructed in Exercise 10.4.1(c),
construct 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 ﬁnd communities.
But communities are in practice rarely disjoint. In this section, we explain a
method for taking a social graph and ﬁtting 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 ﬁnding overlapping communities.
10.5.1
The Nature of Communities
To begin, let us consider what we would expect two overlapping communities
to look like. Our data is a social graph, where nodes are people and there is an
edge between two nodes if the people are “friends.” Let us imagine that this
graph represents students at a school, and there are two clubs in this school:
the Chess Club and the Spanish Club. It is reasonable to suppose that each of
these clubs forms a community. It is also reasonable to suppose that two people
in the Chess Club are more likely to be friends in the graph because they know
each other from the club. Likewise, if two people are in the Spanish Club, then
there is a good chance they know each other, and are likely to be friends.
What if two people are in both clubs? They now have two reasons why they
might know each other, and so we would expect an even greater probability
that they will be friends in the social graph. Our conclusion is that we expect
edges to be dense within any community, but we expect edges to be even denser
in the intersection of two communities, denser than that in the intersection of
three communities, and so on. The idea is suggested by Fig. 10.19.
10.5.2
Maximum-Likelihood Estimation
Before we see the algorithm for ﬁnding communities that have overlap of the
kind suggested in Section 10.5.1, let us digress and learn a useful modeling
tool called maximum-likelihood estimation, or MLE.
The idea behind MLE
is that we make an assumption about the generative process (the model) that
creates instances of some artifact, for example, “friends graphs.” The model has
parameters that determine the probability of generating any particular instance
of the artifact; this probability is called the likelihood of those parameter values.
