Score and rank convergence of HITS Export

@inproceedings{peserico2009score, abstract = {How many iterations does the (ever more) popular HITS algorithm require to converge in score and, perhaps more importantly, in rank (i.e. to get the nodes of a graph "in the right order")? After pinning down the elusive notion of convergence in rank we provide the first non-trivial bounds on the convergence of HITS. A "worst case" example, requiring a number of iterations superexponential in the size of the target graph to achieve even "mild" convergence, suggests the need for greater caution in the experimental evaluation of the algorithm - as recent results of poor performance (e.g. vs. SALSA) might be due to insufficient iterations, rather than to an intrinsic deficiency of HITS. An almost matching upper bound shows that, as long as one employs exponential acceleration e.g. through a "squaring trick", a polynomial running time (practical in many application domains) always provides strong convergence guarantees.}, address = {New York, NY, USA}, author = {Peserico, Enoch and Pretto, Luca}, booktitle = {SIGIR '09: Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval}, citeulike-article-id = {6098514}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1572120}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/1571941.1572120}, doi = {10.1145/1571941.1572120}, isbn = {978-1-60558-483-6}, keywords = {convergence, hits, link\_analysis, rank}, location = {Boston, MA, USA}, pages = {770--771}, posted-at = {2009-11-11 17:25:55}, priority = {2}, publisher = {ACM}, title = {Score and rank convergence of HITS}, url = {http://dx.doi.org/10.1145/1571941.1572120}, year = {2009} }

TY - CONF ID - peserico2009score L3 - citeulike-article-id:6098514 N2 - How many iterations does the (ever more) popular HITS algorithm require to converge in score and, perhaps more importantly, in rank (i.e. to get the nodes of a graph "in the right order")? After pinning down the elusive notion of convergence in rank we provide the first non-trivial bounds on the convergence of HITS. A "worst case" example, requiring a number of iterations superexponential in the size of the target graph to achieve even "mild" convergence, suggests the need for greater caution in the experimental evaluation of the algorithm - as recent results of poor performance (e.g. vs. SALSA) might be due to insufficient iterations, rather than to an intrinsic deficiency of HITS. An almost matching upper bound shows that, as long as one employs exponential acceleration e.g. through a "squaring trick", a polynomial running time (practical in many application domains) always provides strong convergence guarantees. CY - Boston, MA, USA SN - 978-1-60558-483-6 AD - New York, NY, USA EP - 771 TI - Score and rank convergence of HITS PB - ACM T2 - SIGIR '09: Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval SP - 770 KW - convergence KW - hits KW - link_analysis KW - rank AU - Peserico, Enoch AU - Pretto, Luca PY - 2009/// UR - http://dx.doi.org/10.1145/1571941.1572120 ER -