Link analysis ranking.
Published: 2004
Language: eng
Number of pages: 159
Description: The plethora of Link Analysis Ranking algorithms generates the necessity for a formal way to evaluate their properties and compare their behavior. We introduce a theoretical framework for the study of Link Analysis Ranking algorithms, and we define specific properties of the algorithms within this framework. Using these properties we are able to provide an axiomatic characterization of the INDEGREE algorithm that ranks pages according the number of in-coming links.The explosive growth and the widespread accessibility of the Web has led to surge of research activity in the area of information retrieval on the World Wide Web. Ranking has always been an important component of any information retrieval system. In the case of Web search its importance becomes critical. Due to the size of the Web, it is imperative to have ranking functions that capture the user needs. To this end the Web offers a rich context of information which is expressed through the hyperlinks. In this thesis we investigate, theoretically and experimentally, the application of Link Analysis  to ranking on the Web.Building upon the framework of hubs and authorities [57], we propose new families of Link Analysis Ranking algorithms. Some of the algorithms we define no longer enjoy the linearity property of the previous algorithms. As a result, it is harder to analyze them, or even prove that they actually converge. However, for a special case of the families we consider, we are able to prove that it will converge, and we provide a complete characterization of the combinatorial properties of the stationary authority weights it produces.We conclude the thesis with an extensive experimental evaluation of Link Analysis Ranking. We test the algorithms over multiple queries, and we use user feedback to determine their quality. Our experiments reveal some of the limitations of Link Analysis Ranking. Specifically, it appears that for most algorithms, the nodes and the structures in the graph that they favor, do not correspond to the most relevant pages in the collection. These observations offer a new insight into the mechanics of the algorithms, and we believe that they will lead to improved algorithm design, and better input graphs for the algorithms.
Notes: Adviser: Allan Borodin.

Thesis (Ph.D.)--University of Toronto, 2004.

Electronic version licensed for access by U. of T. users.

Source: Dissertation Abstracts International, Volume: 65-05, Section: B, page: 2484.