Seminario Interdipartimentale di Algoritmica
 
 
 

D(S)I - Dipartimento di Informatica, via Salaria 113
Aula Seminari, piano terzo

Abstract:
Recently, there has been a surge of research activity in the area
of Link Analysis Ranking, where hyperlink structures are
used to determine the relative authority of Web pages. One
of the seminal works in this area is that of Kleinberg,
who introduced the hubs and authorities paradigm, and proposed
the HITS algorithm. In this work, we undertake a theoretical
analysis of the properties of the HITS algorithm. Working
within the framework of Borodin et al., we
provide conditions for the stability of the HITS algorithm,
improving upon previous results by Ng, Zheng and
Jordan. Furthermore, we consider the behavior of the
HITS algorithm on a broad class of random graphs, and we prove
that, with high probability it is stable, and it is similar to
the InDegree algorithm, the simple heuristic that assigns to
each node weight proportional to the number of incoming links.
We also investigate the conditions under which the HITS and InDegree
algorithms are similar.
This is joint work with Deborah Donato and Stefano Leonardi