398
CHAPTER 10. MINING SOCIAL-NETWORK GRAPHS
! Exercise 10.6.3: Repeat the analysis of Example 10.24, and compute the
similarities of Picture 1 to the other pictures, if the following modiﬁcations are
made to Fig. 10.22:
(a) The tag “Tree” is added to Picture 2.
(b) A third tag “Water” is added to Picture 3.
(c) A third tag “Water” is added to both Picture 1 and Picture 2.
Note: the changes are independently done for each part; they are not cumula-
tive.
Exercise 10.6.4: Continue the simulation started in Fig. 10.23, assuming the
next three values for U are Picture1, Sky, and Tree.
Exercise 10.6.5: What is the smallest value of ǫ for which we can say that
Fig. 10.23 is the complete execution of the approximate PageRank algorithm?
!! Exercise 10.6.6: Suppose our network consists of only two nodes with an
edge between them. Let the nodes be S (the source, to which teleports occur)
and T , the other node.
(a) Suppose that we run a modiﬁed version of the approximate-PageRank al-
gorithm of Section 10.6.3, where all (rather than only half) of the untaxed
residual of the selected node is distributed to its neighbors (in this case,
to the one neighbor). What is the sequence of values for the vectors r and
q that results? Note that in this case, the choice of U is deterministic,
since at any step only one of the two nodes has residual PageRank. For
very small ǫ, what is the limit of the approximate PageRank vector?
(b) Suppose that for the same network, we instead run the original algorithm,
where only half the residual is distributed to the neighbor. What is the
limiting PageRank in this case, assuming ǫ is tiny?
Exercise 10.6.7: For the network of Fig. 10.22, compute the simrank when
the source node is Tree. Then ﬁnd the best choice of communities containing
Tree if your requirement on a community is
(a) Density at least 2/3.
(b) Local minimum in conductance.
! Exercise 10.6.8: Suppose our network consists of nodes in a single chain, that
is, nodes U1, U2, . . . , Un, with an edge between Ui and Ui+1, for 1 ≤i < n.
(a) As a function of k, compute the density of the “community” consisting of
the ﬁrst k nodes: {U1, U2, . . . , Uk.
