Link Analysis - Mining of Massive Datasets - page 166

be spider traps in G . Then, we restore the graph, but keep the PageRank values for the
nodes of G . Nodes not in G , but with predecessors all in G can have their PageRank com-
puted by summing, over all predecessors p , the PageRank of p divided by the number of
successors of p in the full graph. Now there may be other nodes, not in G , that have the
PageRank of all their predecessors computed. These may have their own PageRank com-
puted by the same process. Eventually, all nodes outside G will have their PageRank com-
puted; they can surely be computed in the order opposite to that in which they were deleted.
EXAMPLE 5.4 Figure 5.4 is a variation on Fig. 5.3 , where we have introduced a successor
E for C . But E is a dead end, and when we remove it, and the arc entering from C , we find
that C is now a dead end. After removing C , no more nodes can be removed, since each of
A , B , and D have arcs leaving. The resulting graph is shown in Fig. 5.5 .
Figure 5.4 A graph with two levels of dead ends
Figure 5.5 The reduced graph with no dead ends
The matrix for the graph of Fig. 5.5 is
The rows and columns correspond to A , B , and D in that order. To get the PageRanks for
this matrix, we start with a vector with all components equal to 1/3, and repeatedly mul-
tiply by M . The sequence of vectors we get is
We now know that the PageRank of A is 2/9, the PageRank of B is 4/9, and the PageRank
of D is 3/9. We still need to compute PageRanks for C and E , and we do so in the order
opposite to that in which they were deleted. Since C was last to be deleted, we know all