Link analysis, eigenvectors, and stability

The HITS and the PageRank algorithms are eigenvector methods for identifying “authoritative” or “influential” articles, given hyperlink or citation information. That such algorithms should give consistent answers is surely a desideratum, and in this paper, we address the question of when they can be expected to give stable rankings under small perturbations to the hyperlink patterns. Using tools from matrix perturbation theory and Markov chain theory, we provide conditions under which these methods are stable, and give specific examples of instability when these conditions are violated. We also briefly describe a modification to HITS that improves its stability. Authors: Andrew Y. Ng, Alice X. Zheng, Michael Jordan (2001)
AUTHORED BY
Andrew Y. Ng
Alice X. Zheng
Michael Jordan

Abstract

The HITS and the PageRank algorithms are eigenvector methods for identifying “authoritative” or “influential” articles, given hyperlink or citation information. That such algorithms should give consistent answers is surely a desideratum, and in this paper, we address the question of when they can be expected to give stable rankings under small perturbations to the hyperlink patterns. Using tools from matrix perturbation theory and Markov chain theory, we provide conditions under which these methods are stable, and give specific examples of instability when these conditions are violated. We also briefly describe a modification to HITS that improves its stability.

Download PDF

No Related Item Available

Leave a Reply

You must be logged in to post a comment