Authority Rankings from HITS, PageRank, and SALSA: Existence, Uniqueness, and Effect of Initialization
Authors:
- Ayman FarahatAFAyman Farahat
- Thomas LoFaroTLThomas LoFaro
- Joel C. MillerJMJoel C. Miller
- Gregory RaeGRGregory Rae
- Lesley A. WardLWLesley A. Ward
- 1 January 2006
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Scientific Computing
- Vol. 27 (4) , 1181-1201
Abstract
Algorithms such as Kleinberg's HITS algorithm, the PageRank algorithm of Brin and Page, and the SALSA algorithm of Lempel and Moran use the link structure of a network of web pages to assign weights to each page in the network. The weights can then be used to rank the pages as authoritative sources. These algorithms share a common underpinning; they find a dominant eigenvector of a nonnegative matrix that describes the link structure of the given network and use the entries of this eigenvector as the page weights. We use this commonality to give a unified treatment, proving the existence of the required eigenvector for the PageRank, HITS, and SALSA algorithms, the uniqueness of the PageRank eigenvector, and the convergence of the algorithms to these eigenvectors. However, we show that the HITS and SALSA eigenvectors need not be unique. We examine how the initialization of the algorithms affects the final weightings produced. We give examples of networks that lead the HITS and SALSA algorithms to returnnonunique or nonintuitive rankings. We characterize all such networks in terms of the connectivity of the related HITS authority graph. We propose a modification, Exponentiated Input to HITS, to the adjacency matrix input to the HITS algorithm. We prove that Exponentiated Input to HITS returns a unique ranking, provided that the network is weakly connected. Our examples also show that SALSA can give inconsistent hub and authority weights, due to nonuniqueness. We also mention a small modification to the SALSA initialization which makes the hub and authority weights consistent.Keywords
This publication has 13 references indexed in Scilit:
- Finding authorities and hubs from link structures on the World Wide Web2001
- The stochastic approach for link-structure analysis (SALSA) and the TKC effectComputer Networks, 2000
- The Many Proofs and Applications of Perron’s TheoremSIAM Review, 2000
- Authoritative sources in a hyperlinked environmentJournal of the ACM, 1999
- Mining the Web's link structureComputer, 1999
- Improved algorithms for topic distillation in a hyperlinked environment1998
- The anatomy of a large-scale hypertextual Web search engineComputer Networks and ISDN Systems, 1998
- Automatic resource compilation by analyzing hyperlink structure and associated textComputer Networks and ISDN Systems, 1998
- Inferring Web communities from link topology1998
- Matrix Analysis1985