Database Reference
In-Depth Information
We must find the values of
p
C
and
p
D
that maximize the above expression. First, notice
that all factors are either independent of
p
C
or grow with
p
C
. The only hard step in this ar-
gument is to remember that
p
D
≤ 1, so
p
C
+
p
D
−
p
C
p
D
must grow positively with
p
C
. It follows that the likelihood is maximized when
p
C
is as
large as possible; that is,
p
C
= 1.
Next, we must find the value of
p
D
that maximizes the expression, given that
p
C
= 1. The
expression becomes
p
D
(1 −
p
D
), and it is easy to see that this expression has its maximum
at
p
D
= 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.
□
However,
Example 10.22
reflects only part of the solution. We also need to find an as-
signment of members to communities such that the maximum likelihood solution for that
assignment is the largest solution for any assignment. Once we fix on an assignment, we
can find the probabilities,
p
C
, associated with each community, even for very large graphs
with large numbers of communities. The general method for doing so is called “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 com-
munity into the gradient-descent solution, since changes to the composition 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 and making small changes, say insertion or
deletion of one member for one community. For each such assignment, we can solve for
the best community probabilities (the
p
C
) by gradient descent. However, figuring out what
changes to membership lead us in the right direction is tricky, and there is no guarantee you
can even get to the best assignment by making incremental changes from a starting assign-
ment.
10.5.4
Avoiding the Use of Discrete Membership Changes
There is a solution to the problem caused by the mechanism of
Section 10.5.3
,
where mem-
bership of individuals in communities is discrete; either you are a member of the commu-
nity or not. We can think of “strength of membership” of individuals in communities. In-
tuitively, the stronger the membership of two individuals in the same community, the more
