Databases Reference
In-Depth Information
2
4
3
5
2
4
3
5
1
0.3583
0
0.7165
0
0.2087
1
1
0.7913
0
h =
a =
This result makes sense. First, we notice that the hubbiness of E is surely 0,
since it leads nowhere. The hubbiness of C depends only on the authority of E
and vice versa, so it should not surprise us that both are 0. A is the greatest
hub, since it links to the three biggest authorities, B, C, and D. Also, B and
C are the greatest authorities, since they are linked to by the two biggest hubs,
A and D.
For Web-sized graphs, the only way of computing the solution to the hubs-
and-authorities equations is iteratively. However, for this tiny example, we
can compute the solution by solving equations.
We shall use the equations
h = λLL
T
h. First, LL
T
is
2
3
3
1
0
2
0
4
5
1
2
0
0
0
LL
T
=
0
0
1
0
0
2
0
0
2
0
0
0
0
0
0
Let ν = 1/(λ) and let the components of h for nodes A through E be a through
e, respectively. Then the equations for h can be written
νa = 3a + b + 2d
νb = a + 2b
νc = c
νd = 2a + 2d
νe = 0
The equation for b tells us b = a/(ν−2) and the equation for d tells us d =
2a/(ν−2). If we substitute these expressions for b and d in the equation for a,
we get νa = a
. From this equation, since a is a factor of both sides,
we are left with a quadratic equation for ν which simplifies to ν
2
−5ν + 1 = 0.
The positive root is ν = (5 +
3+5/(ν−2)
√
21)/2 = 4.791. Now that we know ν is neither
0 or 1, the equations for c and e tell us immediately that c = e = 0.
Finally, if we recognize that a is the largest component of h and set a = 1,
we get b = 0.3583 and d = 0.7165. Along with c = e = 0, these values give us
the limiting value of h. The value of a can be computed from h by multiplying
by A
T
and scaling.
2
5.5.3 Exercises for Section 5.5
Exercise 5.5.1 : Compute the hubbiness and authority of each of the nodes in
our original Web graph of Fig. 5.1.
