384
CHAPTER 10. MINING SOCIAL-NETWORK GRAPHS
4. If a pair of nodes is in two or more communities, then there is an edge be-
tween them if any of the communities of which both are members induces
that edge according to Rule (3).
5. The decision whether a community induces an edge between two of its
members is independent of that decision for any other community of which
these two individuals are also members.
We must compute the likelihood that a given graph with the proper number
of nodes is generated by this mechanism. The key observation is how the edge
probabilities are computed, given an assignment of individuals to communities
and values of the pC’s. Consider an edge (u, v) between nodes u and v. Suppose
u and v are members of communities C and D, but not any other communities.
Then because of the indepenence assumption, Rule (5) above, the probability
that there is no edge between u and v is the product of the probabilities that
there is no edge due to community C and no edge due to community D. That
is, with probability (1 −pC)(1 −pD) there is no edge (u, v) in the graph, and
of course the probability that there is such an edge is 1 minus that.
More generally, if u and v are members of a nonempty set of communities
M and not any others, then puv, the probability of an edge between u and v is
given by:
puv = 1 −
Y
C in M
(1 −pC)
(10.1)
As an important special case, if u and v are not in any communities together,
then we take puv to be ǫ, some very tiny number.
We have to choose this
probability to be nonzero, or else we can never assign a nonzero likelihood
to any set of communities that do not have every pair of individuals sharing
a community.
But by taking the probability to be very small, we bias our
computation to favor solutions such that every observed edge is explained by
joint membership in some community.
If we know which nodes are in which communities, then we can compute
the likelihood of the given graph for these edge probabilities using a simple
generalization of Example 10.21. Let puv be the probability of an edge between
nodes u and v, as deﬁned by Equation (10.1), or ǫ if u and v do not share
a community. Then the likelihood of E being exactly the set of edges in the
observed graph is
Y
(u,v) in E
puv
Y
(u,v) not in E
(1 −puv)
Example 10.22 : Consider the tiny social graph in Fig. 10.20. Suppose there
are two communities C and D, with associated probabilities pC and pD. Also,
suppose that we have determined (or are using as a temporary hypothesis) that
C = {w, x, y} and D = {w, y, z}. To begin, consider the pair of nodes w and
x. Mwx = {C}; that is, this pair is in community C but not in community D.
Therefore, pwx = 1 −(1 −pC) = pC.
