10.6. SIMRANK
389
Exercise 10.5.2: Compute the MLE for the graph in Example 10.22 for the
following guesses of the memberships of the two communities.
(a) C = {w, x}; C = {y, z}.
(b) C = {w, x, y, z}; C = {x, y, z}.
Exercise 10.5.3: Example 10.22 considered the initial assignment of nodes to
two communities C = {w, x, y} and D = {w, y, z}. Suppose we keep the number
of communities ﬁxed at 2, but allow incremental changes to the communities
that add or delete a single node. What would be the ﬁnal assignment of nodes
to the communities C and D that maximizes the likelihood of seeing the graph
of Fig. 10.20? What is that likelihood?
! Exercise 10.5.4: Are there any other assignments of nodes to (any number
of) communities for Fig. 10.20 that would lead to the same likelihood as the
solution you obtained for Exercise 10.5.3?
Exercise 10.5.5: Suppose we have a coin, which may not be a fair coin, and
we ﬂip it some number of times, seeing h heads and t tails.
(a) If the probability p of getting a head on any ﬂip is p, what is the MLE
for p, in terms of h and t?
! (b) Suppose we are told that there is a 90% probability that the coin is fair
(i.e., p = 0.5), and a 10% chance that p = 0.1. For what values of h and
t is it more likely that the coin is fair?
!! (c) Suppose the a-priori likelihood that p has a particular value is proportional
to |p −0.5|. That is, p is more likely to be near 0 or 1, than around 1/2.
If we see h heads and t tails, what is the maximum likelihood estimate of
p?
10.6
Simrank
In this section, we shall take up another approach to analyzing social-network
graphs. This technique, called “simrank,” applies best to graphs with several
types of nodes, although it can in principle be applied to any graph.
The
purpose of simrank is to measure the similarity between nodes of the same
type, and it does so by seeing where random walkers on the graph wind up
when starting at a particular node, the source node. Because calculation must
be carried out once for each source node, there is a limit to the size of graphs
that can be analyzed completely in this manner. However, we shall also oﬀer
an algorithm that approximates simrank, but is far more eﬃcient than iterated
matrix-vector multiplication. Finally, we show how simrank can be used to ﬁnd
communities.
