10.6. SIMRANK
391
10.6.2
Random Walks with Restart
We see from the observations above that it is not possible to measure similar-
ity to a particular 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 walking at random. Later, we saw in Sec-
tion 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 surﬁng
the Web at random.
Here, we take this idea to the extreme. We are focused on one particular
source node S of a social network, and we want to see where the random walker
winds up on short walks from S. To learn where the walker would tend to be,
we modify the matrix of transition probabilities to have a small probability of
transitioning back to S from any node. That is, we shall compute the topic-
sensitive PageRank calculation with a teleport set consisting of only the node
S. 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 ﬁrst, 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 pictures, 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 Picture 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.
Picture 1
Picture 2
Picture 3
Tree
Sky
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


0
0
0
1/3
1/2
0
0
0
1/3
0
0
0
0
1/3
1/2
1/2
1
1/2
0
0
1/2
0
1/2
0
0


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
