392
CHAPTER 10. MINING SOCIAL-NETWORK GRAPHS
nonzero entries in its column must be 1/3. The picture nodes correspond to the
ﬁrst three rows and columns, so the entry 1/3 appears in the ﬁrst three rows
of column 4. Since the “Sky” node does not have an edge to either itself or the
“Tree” node, the entries in the last two rows of column 4 are 0.
✷
As before, let us use β as the probability that the walker continues at ran-
dom, so 1 −β is the probability the walker will teleport to the source node S.
Let eS be the column vector that has 1 in the row for node S and 0’s elsewhere.
Then if v is the column vector that reﬂects the probability the walker is at each
of the nodes at a particular round, and v′ is the probability the walker is at
each of the nodes at the next round, then v′ is related to v by:
v′ = βMv + (1 −β)eS
Example 10.24 : Assume M is the matrix of Example 10.23 and β = 0.8. Also,
assume that node S is Picture 1; that is, we want to compute the similarity
of other pictures to Picture 1. Then the equation for the new value v′ of the
distribution that we must iterate is
v′ =


0
0
0
4/15
2/5
0
0
0
4/15
0
0
0
0
4/15
2/5
2/5
4/5
2/5
0
0
2/5
0
2/5
0
0


v +


1/5
0
0
0
0


Since the graph of Fig. 10.22 is connected, the original matrix M is stochas-
tic, and we can deduce that if the initial vector v has components that sum to
1, then v′ will also have components that sum to 1. As a result, we can simplify
the above equation by adding 1/5 to each of the entries in the ﬁrst row of the
matrix. That is, we can iterate the matrix-vector multiplication
v′ =


1/5
1/5
1/5
7/15
3/5
0
0
0
4/15
0
0
0
0
4/15
2/5
2/5
4/5
2/5
0
0
2/5
0
2/5
0
0


v
If we start with v = eS, then the sequence of estimates of the distribution of
the walker that we get is


1
0
0
0
0


,


1/5
0
0
2/5
2/5


,


35/75
8/75
20/75
6/75
6/75


,


95/375
8/375
20/375
142/375
110/375


,


2353/5625
568/5625
1228/5625
786/5625
690/5625


, . . . ,


.345
.066
.145
.249
.196


We observe from the above that in the limit, the walker is more than twice as
likely to be at Picture 3 than at Picture 2. This analysis conﬁrms the intuition
that Picture 3 is more like Picture 1 than Picture 2 is.
✷
