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.
2009
Proc. of COCOON'09
9783642028816
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11577/2373713
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 4
social impact