The rank convergence of HITS can be slow

Simple item page
dc.creatorPeserico, Enoch
dc.creatorPretto, Luca
dc.date2008-07-18
dc.date.accessioned2026-07-07T09:51:20Z
dc.date.available2026-07-07T09:51:20Z
dc.descriptionWe 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 multiplications even with a "squaring trick"). Our proof requires no algebraic tools and is entirely self-contained.
dc.description5 pages, 1 figure. Keywords: algorithm analysis, information retrieval, rank convergence
dc.identifierhttps://arxiv.org/abs/0807.3006
dc.identifierhttp://arxiv.org/abs/0807.3006
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/165256
dc.subjectData Structures and Algorithms
dc.subjectInformation Retrieval
dc.subjectF.2.2; H.3.3
dc.titleThe rank convergence of HITS can be slow
dc.typetext

Files

Collections

arXiv