Mining Social-Network Graphs - Mining of Massive Datasets - page 361

ated with the tag “Sky” (an uninteresting question in this small example, since there is only
one other tag), then we would have to arrange to have the walker teleport only to the “Sky”
node.
Second, notice that convergence takes time, since there is an initial oscillation. That is,
initially, all the weight is at the pictures, and at the second step most of the weight is at the
tags. At the third step, most weight is back at the pictures, but at the fourth step much of the
weight moves to the tags again. However, in the limit there is convergence, with 5/9 of the
weight at the pictures and 4/9 of the weight at the tags. In general, the process converges
for any connected k -partite graph.

10.6.3 Exercises for Section 10.6

EXERCISE 10.6.1 If, in Fig. 10.22 , you start the walk from Picture 2, what will be the sim-
ilarity to Picture 2 of the other two pictures? Which do you expect to be more similar to
Picture 2?

EXERCISE 10.6.2 If, in Fig. 10.22 , you start the walk from Picture 3, what do you expect
the similarity to the other two pictures to be?

! 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 modifications 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 cumulative.

10.7 Counting Triangles
One of the most useful properties of social-network graphs is the count of triangles and
other simple subgraphs. In this section we shall give methods for estimating or getting an
exact count of triangles in a very large graph. We begin with a motivation for such counts
and then give some methods for counting efficiently.