10.6. SIMRANK
395
Suppose we then choose Tree as the next value of node U. The value of
qT r is now 0.2, so we move one ﬁfth of this value to rT r, which makes that
value be 0.04. Of the remaining 0.16, half remains as qT r, and the remainder is
divided between qP 1, which becomes 0.44, and qP 3, which becomes 0.04. These
steps explain the third row. We show a sequence of three additional steps, each
with a possible choice of U, assuming ǫ is large enough to justify continuing
the algorithm. You are invited to work the next three steps by yourself and
continue the simulation, which is shown only to three decimal places.
✷
10.6.4
Why Approximate Simrank Works
There are several questions you may naturally ask about the algorithm de-
scribed in the previous section.
1. Why is this algorithm more eﬃcient than the straightforward implemen-
tation of PageRank with a single source node as the teleport set?
2. Why does this algorithm converge to an approximation of the true sim-
rank?
3. Why do we distribute only half the residual value for node U, rather than
the entire residual?
The answer to the last question is simplest. It is there to help distribute the
residual values as quickly as possible. For some graphs, it is ﬁne to skip step (3)
and in step (4) to give each node V an additional residual of βqU/d. However,
in other cases, such as a bipartite graph, distributing the entire residual of node
U will cause the residuals to bounce back and forth between the two sides of
the graph, thus causing there to be at least one large residual for a longer time,
than if we distributed only half the residual.
For the ﬁrst question, we note that every node that qualiﬁes as a possible
choice of U has qU > ǫ; usually it will be comsiderably larger than ǫ because the
actual lower bound on qU is ǫ times the degree of U. Observe that if qU > ǫ,
then a quantity of at least ǫ(1 −β) is moved from the residual vector q to
the approximate PageRank vector r. However, the sum of all the components
of both vectors is 1, so we cannot have a number of rounds of this algorithm
that exceeds
1
ǫ(1−β). That is a constant number of rounds, while the customary
PageRank algorithm takes time that is at least proportional to the number of
nodes in the graph times the number of iterations of matrix-vector multiplica-
tion. Further, if we are careful, we can organize the components of q into a
priority queue, so we can select a candidate for U in O(log n) time if there are
n nodes in the graph.
Finally, we need to address the second question: why does the result approx-
imate the true simrank? Here is an intuitive argument. First, moving residual
values around the graph is a simulation of random walkers on the graph. The
fact that the walkers are moving asynchronously (since they move with 50%
