The rank convergence of HITS can be slow

Enoch Peserico, Luca Pretto

We prove that HITS, to "get right" h of the top k ranked nodes of an N>=2k node graph, can require h^(Omega(N h/k)) iterations (i.e. a substantial Omega(N h log(h)/k) matrix multip…