10.5. FINDING OVERLAPPING COMMUNITIES
385
y
z
w
x
Figure 10.20: A social graph
Similarly, x and y are only together in C, y and z are only together in D,
and likewise w and z are only together in D. Thus, we ﬁnd pxy = pC and
pyz = pwz = pD. Now the pair w and y are together in both communities, so
pwy = 1−(1−pC)(1−pD) = pC +pD −pCpD. Finally, x and z are not together
in either community, so pxz = ǫ.
Now, we can compute the likelihood of the graph in Fig. 10.20, given our
assumptions about membership in the two communities. This likelihood is the
product of the probabilities associated with each of the four pairs of nodes
whose edges appear in the graph, times one minus the probability for each of
the two pairs whose edges are not there. That is, we want
pwxpwypxypyz(1 −pwz)(1 −pxz)
Substituting the expressions we developed above for each of these probabilities,
we get
(pC)2pD(pC + pD −pCpD)(1 −pD)(1 −ǫ)
(10.2)
Note that ǫ is very small, so the last factor is essentially 1 and can be dropped.
We must ﬁnd the values of pC and pD that maximize Expression (10.2).
First, notice that all factors are either independent of pC or grow with pC. The
only hard step in this argument is to remember that pD ≤1, so
pC + pD −pCpD
must grow positively with pC. It follows that the likelihood is maximized when
pC is as large as possible; that is, pC = 1.
Next, we must ﬁnd the value of pD that maximizes the expression, given
that pC = 1. The expression becomes pD(1 −pD), and it is easy to see that
this expression has its maximum at pD = 0.5. That is, given C = {w, x, y} and
D = {w, y, z}, the maximum likelihood for the graph in Fig. 10.20 occurs when
members of C are certain to have an edge between them and there is a 50%
chance that joint membership in D will cause an edge between the members.
✷
10.5.4
Discrete Optimization of Community Assignments
Example 10.22 reﬂects only part of the process whereby we develop an aﬃliation-
graph model for a given network. We also need to ﬁnd an assignment of mem-
