Database Reference
In-Depth Information
That outcome is hardly a surprise. It says the most likely value for
p
is the observed frac-
tion of possible edges that are present in the graph. However, when we use a more com-
plicated mechanism to generate graphs or other artifacts, the value of the parameters that
produce the observed artifact with maximum likelihood is far from obvious.
□
10.5.3
The Affiliation-Graph Model
We shall now introduce a reasonable mechanism, called the
affiliation-graph model
, to gen-
erate social graphs from communities. Once we see how the parameters of the model in-
fluence the likelihood of seeing a given graph, we can address how one would solve for
the values of the parameters that give the maximum likelihood. The mechanism, called
community-affiliation graphs
, states:
(1) There is a given number of communities, and there is a given number of individuals
(nodes of the graph).
(2) Each community can have any set of individuals as members. That is, the member-
ships in the communities are parameters of the model.
(3) Each community
C
has a probability
p
C
associated with it, the probability that two
members of community
C
are connected by an edge because they are both members
of
C
. These probabilities are also parameters of the model.
(4) If a pair of nodes is in two or more communities, then there is an edge between them
if any of the communities of which both are members justifies that edge according to
rule (3)
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 com-
puted, given an assignment of individuals to communities and values of the
p
C
. 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 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 −
p
C
)(1 −
p
D
) 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
p
uv
, the probability of an edge between
u
and
v
is given by:
As an important special case, if
u
and
v
are not in any communities together, then we take
p
uv
to be
ϵ
, some very tiny number. We have to choose this probability to be nonzero, or else
