Database Reference
In-Depth Information
out. This conclusion comes from the theory of Markov processes that we mentioned in
Sec-
tion 5.1.2
,
although the independence from the starting point requires additional conditions
besides connectedness that the graph of
Fig. 10.21
does satisfy.
10.6.2
Random Walks with Restart
We see from the observations above that it is not possible to measure similarity to a partic-
ular node by looking at the limiting distribution of the walker. However, we have already
seen, in
Section 5.1.5
,
the introduction of a small probability that the walker will stop walk-
ing at random. Later, we saw in
Section 5.3.2
that there were reasons to select only a subset
of Web pages as the teleport set, the pages that the walker would go to when they stopped
surfing the Web at random.
Here, we take this idea to the extreme. As we are focused on one particular node
N
of
a social network, and want to see where the random walker winds up on short walks from
that node, we modify the matrix of transition probabilities to have a small additional prob-
ability of transitioning to
N
from any node. Formally, let
M
be the
transition matrix
of the
graph
G
. That is, the entry in row
i
and column
j
of
M
is 1
/k
if node
j
of
G
has degree
k
, and
one of the adjacent nodes is
i
. Otherwise, this entry is 0. We shall discuss teleporting in a
moment, but first, let us look at a simple example of a transition matrix.
EXAMPLE
10.23
Figure 10.22
is an example of a very simple network involving three pic-
tures, and two tags, “Sky” and “Tree” that have been placed on some of them. Pictures 1
and 3 have both tags, while Picture 2 has only the tag “Sky.” Intuitively, we expect that Pic-
ture 3 is more similar to Picture 1 than Picture 2 is, and an analysis using a random walker
with restart at Picture 1 will support that intuition.
Figure 10.22
A simple bipartite social graph
Let us order the nodes as Picture 1, Picture 2, Picture 3, Sky, Tree. Then the transition
matrix for the graph of
Fig. 10.22
is
For example, the fourth column corresponds to the node “Sky,” and this node connects to
each of the tree picture nodes. It therefore has degree three, so the nonzero entries in its
