Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
Stability and Similarity of Link Analysis Ranking Algorithms
verfasst von : Debora Donato, Stefano Leonardi, Panayiotis Tsaparas
Erschienen in: Automata, Languages and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 [15], who proposed the
Hits
algorithm. In this paper, we undertake a theoretical analysis of the properties of the
Hits
algorithm on a broad class of random graphs. Working within the framework of Borodin et al.[7], we prove that on this class (a) the
Hits
algorithm is stable with high probability, and (b) the
Hits
algorithm is similar to the
InDegree
heuristic that assigns to each node weight proportional to the number of incoming links. We demonstrate that our results go through for the case that the expected in-degrees of the graph follow a power-law distribution, a situation observed in the actual Web graph [9]. We also study experimentally the similarity between
Hits
and
InDegree
, and we investigate the general conditions under which the two algorithms are similar.