Databases Reference
In-Depth Information
the PageRank values for the nodes of G. Nodes not in G, but with predecessors
all in G can have their PageRank computed 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 computed by
the same process. Eventually, all nodes outside G will have their PageRank
computed; they can surely be computed in the order opposite to that in which
they were deleted.
A
B
C
D
E
Figure 5.4: A graph with two levels of dead ends
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.
The matrix for the graph of Fig. 5.5 is
2
3
0
1/2
0
4
5
M =
1/2
0
1
1/2
1/2
0
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 multiply by M . The sequence of vectors we get is
2
3
2
3
2
3
2
3
2
3
1/3
1/3
1/3
1/6
3/6
2/6
3/12
5/12
4/12
5/24
11/24
8/24
2/9
4/9
3/9
4
5
4
5
4
5
4
5
4
5
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
