Database Reference
In-Depth Information
The fact that the hubbiness of a page is proportional to the sum of the au thority of its suc-
cessors is expressed by the equation
h
= λ
L
a
, where λ is an unknown constant representing
the scaling factor needed. Likewise, the fact that the authority of a page is proportional to
the sum of the hubbinesses of its predecessors is expressed by
a
=
µL
T
h
, where
µ
is another
scaling constant. These equations allow us to compute the hubbiness and authority inde-
pendently, by substituting one equation in the other, as:
•
h
= λ
µLL
T
h
.
•
a
= λ
µL
T
L
a
.
However, since
LL
T
and
L
T
L
are not as sparse as
L
and
L
T
, we are usually better off com-
puting
h
and
a
in a true mutual recursion. That is, start with
h
a vector of all 1s.
(1) Compute
a
=
L
T
h
and then scale so the largest component is 1.
(2) Next, compute
h
=
L
a
and scale again.
Now, we have a new
h
and can repeat steps (1) and (2) until at some iteration the changes
to the two vectors are sufficiently small that we can stop and accept the current values as
the limit.
EXAMPLE
5.15 Let us perform the first two iterations of the HITS algorithm on the Web of
initial
h
, all 1s. In the second column, we have estimated the relative authority of pages by
computing
L
T
h
, thus giving each page the sum of the hubbinesses of its predecessors. The
third column gives us the first estimate of
a
. It is computed by scaling the second column;
in this case we have divided each component by 2, since that is the largest value in the
second column.
Figure 5.20
First two iterations of the HITS algorithm
The fourth column is
L
a
. That is, we have estimated the hubbiness of each page by
summing the estimate of the authorities of each of its successors. Then, the fifth column
scales the fourth column. In this case, we divide by 3, since that is the largest value in the
fourth column. Columns six through nine repeat the process outlined in our explanations
