394
CHAPTER 10. MINING SOCIAL-NETWORK GRAPHS
closer we get to the true PageRank, but also the longer the computation takes.
We should choose ǫ to be very small, say 0.01 divided by the number of edges
in the graph. That way we do not terminate until the total amount of residual
PageRank is at most 0.01. The approximate-simrank algorithm is to repeat the
following steps until we can no longer ﬁnd any node U whose residual PageRank
divided by its degree (i.e., the amount of PageRank it could pass to any one of
its neighbors) is greater than ǫ.
1. Let U be any node such that qU, the component of q for node U, exceeds ǫ
times the degree of U.
2. Add (1 −β)qU to the current value of rU. That is, we credit node U with
an amount of true PageRank equal to the tax on its current residual.
3. Set qU to βqU/2. That is, of the portion of U’s residual that is not taxed,
half that residual remains at U.
4. Suppose U has degree d. Then for each node V adjacent to U, add to
qV an amount equal to βqU/(2d). That is, the other half of the untaxed
residual for U is divided equally among its neighbors.
Example 10.25 : Let us reconsider Example 10.23 from the point of view
of appreoximate PageRank, again using Picture1 as the source node S. We
shall again use β = 0.8, but we shall leave ǫ unspeciﬁed, since we are not
going to carry out the computation to completion for any reasonably small ǫ.
Figure 10.23 summarizes what could be the ﬁrst ﬁve steps of the algorithm.
U
rP 1
rP 2
rP 3
rSk
rT r
‘ qP 1
qP 2
qP 3
qSk
qT r
Initial
0
0
0
0
0
1
0
0
0
0
Picture1
.2
0
0
0
0
.4
0
0
.2
.2
Tree
.2
0
0
0
.04
.44
0
.04
.2
.08
Picture1
.288
0
0
0
.04
.176
0
.04
.288
.168
Sky
.288
0
0
.058
.04
.214
.038
.078
.115
.168
Picture3
.288
0
.016
.058
.04
.214
.038
.031
.131
.184
Figure 10.23: The ﬁrst ﬁve steps in an approximate PageRank calculation
The ﬁrst row, labeled “Initial,” shows the initial values of r and q. We show
each component for each vector, in the same order as in Example 10.23: Pictures
1, 2, and 3, then Sky and Tree. Our ﬁrst choice of U has to be Picture1, the
source node, since it is the only node with any residual PageRank. In step (1)
we convert (1 −β)qP 1 of the residual for Picture1 to approximate PageRank.
Thus, rP 1 is set to 0.2. Of the remaining value 0.8 for qP 1, 0.4 remains, and
the other 0.4 is divided equally among the neighbors Sky and Tree of Picture1.
These observations explain the second row of the table.
