388
CHAPTER 10. MINING SOCIAL-NETWORK GRAPHS
Continuous Versus Discrete Optimization
The trick used in Section 10.5.5 is surprisingly common. Whenever you
are trying to ﬁnd an optimum solution to a problem where some of the
elements are continuous (e.g., the probabilities of communities inducing
edges) and some elements are discrete (e.g., the memberships of the com-
munities), it might make sense to replace each discrete element by a con-
tinuous variable. That change, while it doesn’t strictly speaking represent
reality, enables us to perform only one optimization, which will use a
continuous-optimization method such as gradient descent. Note, however,
that whether we perform a discrete optimization, as in Section 10.5.4 or
a continuous optimization as in Section 10.5.5, we run the risk of winding
up in a local optimum that is not the globally best solution.
for each edge (u, v) that is not in E. Thus, in the new model, the formula for
the likelihood of the graph with edges E is
Y
(u,v) in E
(1 −e−P
C FuCFvC)
Y
(u,v) not in E
e−P
C FuCFvC
(10.3)
We can simplify Expression (10.3) somewhat by taking its logarithm. Re-
member that maximizing a function also maximizes the logarithm of that func-
tion, and vice versa.
So we can take the natural logarithm of the Expres-
sion (10.3) to replace the products by sums. We also get simpliﬁcation from
the fact that log(ex) = x.
X
(u,v) in E
log(1 −e−P
C FuCFvC) −
X
(u,v) not in E
X
C
FuCFvC
(10.4)
We can now ﬁnd the values for the FxC’s that maximizes the expression
(10.4). One way is to use gradient descent in a manner similar to what was
done in Section 9.4.5. That is, we pick one node x, and adjust all the values of
the FxC’s in the direction that most improves the value of (10.4). Notice that
the only factors whose values change in response to changes to the FxC’s are
those where one of u and v is x and the other of u and v is a node adjacent to
x. Since the degree of a node is typically much less than the number of edges
in the graph, we can avoid looking at most of the terms in (10.4) at each step.
10.5.6
Exercises for Section 10.5
Exercise 10.5.1: Suppose graphs are generated by picking a probability p and
choosing each edge independently with probability p, as in Example 10.21. For
the graph of Fig. 10.20, what value of p gives the maximum likelihood of seeing
that graph? What is the probability this graph is generated?
