382
CHAPTER 10. MINING SOCIAL-NETWORK GRAPHS
Chess Club
Spanish Club
Intersection
Figure 10.19: The overlap of two communities is denser than the nonoverlapping
parts of these communities
We assume that the value of the parameters that gives the largest value of the
likelihood is the correct model for the observed artifact.
An example should make the MLE principle clear. For instance, we might
wish to generate random graphs. We suppose that each edge is present with
probability p and not present with probability 1−p, with the presence or absence
of each edge chosen independently. The only parameter we can adjust is p. For
each value of p there is a small but nonzero probability that the graph generated
will be exactly the one we see. Following the MLE principle, we shall declare
that the true value of p is the one for which the probability of generating the
observed graph is the highest.
Example 10.21 : Consider the graph of Fig. 10.19. There are 15 nodes and
23 edges. As there are
15
2

= 105 pairs of 15 nodes, we see that if each edge
is chosen with probability p, then the probability (likelihood) of generating
exactly the graph of Fig. 10.19 is given by the function p23(1 −p)82. No matter
what value p has between 0 and 1, that is an incredibly tiny number. But the
function does have a maximum, which we can determine by taking its derivative
and setting that to 0. That is:
23p22(1 −p)82 −82p23(1 −p)81 = 0
We can group terms to rewrite the above as
p22(1 −p)8123(1 −p) −82p

= 0
