Link Analysis - Mining of Massive Datasets - page 170

!! EXERCISE 5.1.4 Construct, for any integer n , a Web such that, depending on β , any of the
n nodes can have the highest PageRank among those n . It is allowed for there to be other
nodes in the Web besides these n .
! EXERCISE 5.1.5 Show by induction on n that if the second, third, and fourth components
of a vector v are equal, and M is the transition matrix of Example 5.1 , then the second,
third, and fourth components are also equal in M n v for any n ≥ 0.
EXERCISE 5.1.6 Suppose we recursively eliminate dead ends from the graph, solve the re-
maining graph, and estimate the PageRank for the dead-end pages as described in Section
5.1.4 . Suppose the graph is a chain of dead ends, headed by a node with a self-loop, as sug-
gested in Fig. 5.9 . What would be the PageRank assigned to each of the nodes?
Figure 5.9 A chain of dead ends
EXERCISE 5.1.7 Repeat Exercise 5.1.6 for the tree of dead ends suggested by Fig. 5.10 . That
is, there is a single node with a self-loop, which is also the root of a complete binary tree of
n levels.
Figure 5.10 A tree of dead ends
5.2 Efficient Computation of PageRank
To compute the PageRank for a large graph representing the Web, we have to perform a
matrix-vector multiplication on the order of 50 times, until the vector is close to unchanged
at one iteration. To a first approximation, the MapReduce method given in Section 2.3.1 is
suitable. However, we must deal with two issues:
(1) The transition matrix of the Web M is very sparse. Thus, representing it by all its ele-
ments is highly inefficient. Rather, we want to represent the matrix by its nonzero ele-
ments.
(2) We may not be using MapReduce, or for efficiency reasons we may wish to use a com-
biner (see Section 2.2.4 ) with the Map tasks to reduce the amount of data that must be