Databases Reference
In-Depth Information
F
Recursive Formulation of the HITS Algorithm: Calculation of the hubs
and authorities scores for pages depends on solving the recursive equa-
tions: “a hub links to many authorities, and an authority is linked to
by many hubs.” The solution to these equations is essentially an iter-
ated matrix-vector multiplication, just like PageRank's. However, the
existence of dead ends or spider traps does not affect the solution to the
HITS equations in the way they do for PageRank, so no taxation scheme
is necessary.
5.7
References for Chapter 5
The PageRank algorithm was first expressed in [1]. The experiments on the
structure of the Web, which we used to justify the existence of dead ends and
spider traps, were described in [2]. The block-stripe method for performing the
PageRank iteration is taken from [5].
Topic-sensitive PageRank is taken from [6]. TrustRank is described in [4],
and the idea of spam mass is taken from [3].
The HITS (hubs and authorities) idea was described in [7].
1. S. Brin and L. Page, “Anatomy of a large-scale hypertextual web search
engine,” Proc. 7th Intl. World-Wide-Web Conference, pp. 107-117, 1998.
2. A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R.
Stata, A. Tomkins, and J. Weiner, “Graph structure in the web,” Com-
puter Networks 33:1-6, pp. 309-320, 2000.
3. Z. Gyongi, P. Berkhin, H. Garcia-Molina, and J. Pedersen, “Link spam
detection based on mass estimation,” Proc. 32nd Intl. Conf. on Very Large
Databases, pp. 439-450, 2006.
4. Z. Gyongi, H. Garcia-Molina, and J. Pedersen, “Combating link spam
with trustrank,” Proc. 30th Intl. Conf. on Very Large Databases, pp. 576-
587, 2004.
5. T.H. Haveliwala, “E
cient computation of PageRank,” Stanford Univ.
Dept. of Computer Science technical report, Sept., 1999. Available as
http://infolab.stanford.edu/~taherh/papers/efficient-pr.pdf
6. T.H. Haveliwala, “Topic-sensitive PageRank,” Proc. 11th Intl. World-
Wide-Web Conference, pp. 517-526, 2002
7. J.M. Kleinberg, “Authoritative sources in a hyperlinked environment,” J.
ACM 46:5, pp. 604-632, 1999.
