Databases Reference
In-Depth Information
a
b
c
Figure 5.7: An example graph for exercises
Exercise 5.1.2 : Compute the PageRank of each page in Fig. 5.7, assuming
β = 0.8.
! Exercise 5.1.3 : Suppose the Web consists of a clique (set of nodes with all
possible arcs from one to another) of n nodes and a single additional node that
is the successor of each of the n nodes in the clique. Figure 5.8 shows this graph
for the case n = 4. Determine the PageRank of each page, as a function of n
and β.
Figure 5.8: Example of graphs discussed in Exercise 5.1.3
!! 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 Exam-
ple 5.1, then the second, third, and fourth components are also equal in M
n
v
for any n≥0.
