Seminario Interdipartimentale di Algoritmica
 
 
 

Dipartimento di Informatica (ex-Scienze dell'Informazione) - D(S)I
via Salaria 113, piano terzo
Aula Seminari

Abstract:
Ranking is an integral part of any information retrieval system. In the case of the Web, because of its huge size, the frequency of Web search, and the demanding nature of the Web users, ranking becomes even more critical. In the recent years there has been a surge of research activity in the area of Link Analysis Ranking, where the underlying hypertext graph topology is used to rank web pages. We consider some of the previously published algorithms and we introduce some new alternatives.

One of our new algorithms is based on a Bayesian statistical approach as opposed to the more common algebraic/graph theoretic approach. We also examine the application of non-linear dynamical systems for ranking. Although the mathematics for studying non-linear dynamical systems are not as well understood, we prove that the dynamical system we define converges for any initialization, and we study the combinatorial properties of the stationary weights.

We also define a formal framework for the theoretical analysis of Link Analysis Ranking algorithms. Within this framework we formally define various properties such as monotonicity, stability, and similarity. We study the properties of existing algorithms, and we provide an axiomatic characterization of the In-Degree algorithm that ranks each page according to number of links that point to it.