Link Analysis - Mining of Massive Datasets - page 165

M i v for increasing powers of a substochastic matrix M , then some or all of the components
of the vector go to 0. That is, importance “drains out” of the Web, and we get no informa-
tion about the relative importance of pages.

EXAMPLE 5.3 In Fig. 5.3 we have modified Fig. 5.1 by removing the arc from C to A . Thus,
C becomes a dead end. In terms of random surfers, when a surfer reaches C they disappear
at the next round. The matrix M that describes Fig. 5.3 is

Note that it is substochastic, but not stochastic, because the sum of the third column, for C ,
is 0, not 1. Here is the sequence of vectors that result by starting with the vector with each
component 1/4, and repeatedly multiplying the vector by M :

As we see, the probability of a surfer being anywhere goes to 0, as the number of steps
increase. □

Figure 5.3 C is now a dead end

There are two approaches to dealing with dead ends.

(1) We can drop the dead ends from the graph, and also drop their incoming arcs. Doing
so may create more dead ends, which also have to be dropped, recursively. However,
eventually we wind up with a strongly-connected component, none of whose nodes
are dead ends. In terms of Fig. 5.2 , recursive deletion of dead ends will remove parts
of the out-component, tendrils, and tubes, but leave the SCC and the in-component, as
well as parts of any small isolated components. 4
(2) We can modify the process by which random surfers are assumed to move about the
Web. This method, which we refer to as “taxation,” also solves the problem of spider
traps, so we shall defer it to Section 5.1.5 .

If we use the first approach, recursive deletion of dead ends, then we solve the remaining
graph G by whatever means are appropriate, including the taxation method if there might