Seminar on Computational Learning and Adaptation

  Modifications of Kleinberg's HITS Algorithm using Matrix Exponentiation and Web Log Records

Ayman Farahat, Angara, Mountain View, CA

Thomas LoFaro, Gustavus Adolphus College, St. Peter, MN

Joel Miller, Cambridge University, UK

Gregory Rae, Google.com, Mountain View, CA

Fred Schaefer, Statistics Collaborative, Washington DC

Lesley Ward, Harvey Mudd College, Claremont, CA

Kleinberg's HITS algorithm, `Hypertext Induced Topic Selection', is one of the standard algorithms of link analysis. It uses the link structure of a network of webpages to assign authority and hub weights to each page in the network. These weights can then be used to rank sources on a particular topic. We have found that certain tree-like web structures can lead the HITS algorithm to return either arbitrary or non-intuitive results; we characterize these web structures. We present two modifications to the adjacency matrix input to the HITS algorithm. Exponentiated Input, our first modification, includes in the modified matrix information not only on direct links between pages, but also on paths of arbitrary length between pages in the network. It resolves both the limitations mentioned above. Usage Weighted Input, our second modification, weights links according to how often they were followed by users in a given time period; it incorporates user feedback without requiring direct user querying.

Return to the seminar schedule