10.6. SIMRANK
393
There are several additional observations that we may take away from Ex-
ample 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 associated with the tag “Sky” (an uninter-
esting 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 oscil-
lation. 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
Approximate Simrank
The straightforward calculation of simrank involves repeated matrix-vector mul-
tiplications, just as for any PageRank-type calculation. However, when there is
a single node S in the teleport set, nodes that are far from S are certain to get
a very small simrank. If we are willing to accept an approximation to the true
simrank, we can use another approach, where we never even look at the nodes
that are far away from S.
We shall simulate a diﬀerent kind of walk on the graph. Instead of the walker
moving to a random neighbor (if it does not teleport to the source node), it
will either move or stay where it is, with equal probability. If it decides to
move, then it will move to any neighbor with equal probability. However, there
is another aspect to the decision whether to move or not. We can regard a
walker as either part of the limiting PageRank for its node, or part of the
residual PageRank, that is, PageRank that has not yet been assigned to any
node. Only in the latter case do we consider moving that walker.
We shall therefore use two vectors, r and q, each with one component for
each node. In what follows, r will be our current estimates for the PageRank
of each node, and q will be the current residual PageRank for each node. How-
ever, note that as the computation proceeds, we may never compute many of
the components of these vectors. We shall also use the notation qU for the
component of q for node U, and use rU analogously. Initailly, we assume r is
the all-0’s vector, while q is all 0’s except for qS = 1. That is, q says that we
assume all walkers start at S, while r says that we have not yet resolved where
any of them will wind up asymptotically.
The approximate simrank calculation uses two parameters. We continue to
use β as the nontaxed fraction; i.e., 1 −β is the probability that a walker will
teleport to the source node S. The second parameter we need is ǫ, a small
fraction that gives the maximum amount of residual PageRank that we shall
be willing not to pass from one node to a neighbor. Thus, the smaller ǫ is, the
