This paper explores the fundamental question of how many iterations the celebrated HITS algorithm requires on a general graph to converge in score and, perhaps more importantly, in rank (i.e. to ``get right'' the order of the nodes). We prove upper and almost matching lower bounds. We also extend our results to weighted graphs.
HITS can converge slowly, but not too slowly, in score and rank
PESERICO STECCHINI NEGRI DE SALVI, ENOCH;PRETTO, LUCA
2009
Abstract
This paper explores the fundamental question of how many iterations the celebrated HITS algorithm requires on a general graph to converge in score and, perhaps more importantly, in rank (i.e. to ``get right'' the order of the nodes). We prove upper and almost matching lower bounds. We also extend our results to weighted graphs.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
