386
CHAPTER 10. MINING SOCIAL-NETWORK GRAPHS
bers to communities such that the maximum-likelihood solution for that as-
signment has the largest likelihood for any assignment.
Once we ﬁx on an
assignment, we can ﬁnd the probabilities pC associated with each community
C. The most popular method for doing so is “gradient descent,” a technique
that we introduced in Section 9.4.5 and that will be discussed further starting
in Section 12.3.4.
Unfortunately, it is not obvious how one incorporates the set of members of
each community into the gradient-descent solution, since changes to the mem-
bership of communities is by discrete steps, not according to some continuous
function as is required for gradient descent. The only feasible way to search the
space of possible assignments of members to communities is by starting with an
assignment, perhaps chosen at random. As we search for better assignments,
we always have one assignment that is “current.”
We consider small changes to the assignment, say by insertion or deletion
of one member for one community. For each such assignment, we can solve for
the best community probabilities (the pC’s) by gradient descent. If a change
to the current assignment leads to a higher likelihood, then make the resulting
assignment be the current assignment. If the change does not improve the like-
lihood, then try another change from the current assignment. Eventually, you
will reach a current assignment for which no small change to the assignment
leads to a higher likelihood. The resulting assignment, along with the proba-
bilities for the communities that maximizes the likelihood for this assignment,
forms the aﬃliation-graph model for this graph.
Note that because we allow only a particular set of simple changes, such
as insertion or deletion of one member, the resulting assignment of nodes to
communities may not be globally optimum. It is possible that the model with
the highest likelihood is radically diﬀerent from the best assignment we can
reach. It is possible, and often appropriate, to repeat this process with many
diﬀerent random starting solutions, and to take the best of the resulting models.
Finally, in the above discussion we assumed the number of communities
was ﬁxed.
We can also permit “small” changes that adjust the number of
communities, e.g., by merging two communities or by adding a new community
with a random set of initial members. Another approach is to ﬁx the number of
communities, but after ﬁnding the best model for that number of communities,
add one more community and solve again, to see if the likelihood of the best
model improves. If not, subtract one from the number of communities to see if
the likelihood improves. If either of those changes improves things, then repeat
the process of moving in the direction or more or fewer communities, whichever
led to an improvement.
10.5.5
Avoiding the Use of Discrete Membership Changes
There is a solution to the problem caused by the aﬃliation-graph model, where
membership of individuals in communities is discrete: either you are a member
of the community or not. Instead of “all-or-nothing” membership of nodes in
