10.5. FINDING OVERLAPPING COMMUNITIES
387
Log Likelihood
Usually, we compute the logarithm of the likelihood function (the log like-
lihood), rather than the function itself. Doing so oﬀers several advantages.
Products become sums, which often simpliﬁes the expression. Also, sum-
ming many numbers is less prone to numerical rounding errors than is
taking the product of many tiny numbers.
communities, we can suppose that for each node and each community, there
is a “strength of membership” for that node and community. Intuitively, the
stronger the membership of two individuals in the same community is, the more
likely it is that this community will cause there to be an edge between them.
In this model, we can adjust the strength of membership for an individual in a
community continuously, just as we can adjust the probability associated with
a community in the aﬃliation-graph model. That improvement allows us to
use methods for optimizing continuous functions, such as gradient descent, to
maximize the expression for likelihood. In the new model, we have
1. Fixed sets of communities and individuals, as before.
2. For each community C and individual x, there is a strength of membership
parameter FxC. These parameters can take any nonnegative value, and a
value of 0 means the individual is deﬁnitely not in the community.
3. The probability that community C causes there to be an edge between
nodes u and v is
pC(u, v) = 1 −e−FuCFvC
As before, the probability of there being an edge between u and v is 1 minus
the probability that none of the communities causes there to be an edge between
them. That is, each community independently causes edges, and an edge exists
between two nodes if any community causes it to exist. More formally, puv, the
probability of an edge between nodes u and v, is
puv = 1 −
Y
C
1 −pC(u, v)

If we substitute the formula for pC(u, v) that is assumed in the model, we get
puv = 1 −e−P
C FuCFvC
Finally, let E be the set of edges in the observed graph. As before, we can
write the formula for the likelihood of the observed graph as the product of the
expression for puv for each edge (u, v) that is in E, times the product of 1 −puv
