Database Reference
In-Depth Information
column must be 1/3. The picture nodes correspond to the first three rows and columns, so
the entry 1/3 appears in the first 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 random, so 1 −
β
is the probability the walker will teleport to the initial node
N
. Let
e
N
be the column vector
that has 1 in the row for node
N
and 0's elsewhere. Then if
v
is the column vector that re-
flects 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
′ =
βM
v
+ (1 −
β
)
e
N
EXAMPLE
10.24 Assume
M
is the matrix of
Example 10.23
and
β
= 0
.
8. Also, assume that
node
N
is for Picture 1; that is, we want to compute the similarity of other pictures to Pic-
ture 1. Then the equation for the new value
v
′ of the distribution that we must iterate is
Since the graph of
Fig. 10.22
is connected, the original matrix
M
is stochastic, 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 first row of the matrix. That is, we can iterate the matrix-vector
multiplication
If we start with
v
=
e
N
, then the sequence of estimates of the distribution of the walker that
we get is
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 confirms the intuition that Picture 3 is more like
Picture 1 than Picture 2 is.
□
There are several additional observations that we may take away from
Example 10.24
.
First, remember that this analysis applies only to Picture 1. If we wanted to know what
pictures were most similar to another picture, we would have to start the analysis over for
that picture. Likewise, if we wanted to know about which tags were most closely associ-
