A Survey of Eigenvector Methods for Web Information Retrieval
SIAM ReviewPublished 1 January 2005
Amy N. Langville, Carl D. Meyer
Citations435
SJR quartileQ1
SJR score3.02
SNIP5.22
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This survey paper focuses on Web information retrieval methods that use eigenvector computations, presenting the three popular methods of HITS, PageRank, and SALSA.
Abstract
Abstract. Web information retrieval is significantly more challenging than traditional well-controlled, small document collection information retrieval. One main difference between traditional information retrieval and Web information retrieval is the Web’s hyperlink structure. This structure has been exploited by several of today’s leading Web search engines, particularly Google and Teoma. In this survey paper, we focus on Web information retrieval methods that use eigenvector computations, presenting the three popular methods of HITS, PageRank, and SALSA.
Keywords
Computer Science
Computer Networks and ISDN SystemsThe anatomy of a large-scale hypertextual Web search engine
15,828 Citations1998Sergey Brin, Lawrence M. Page
This paper provides an in-depth description of Google, a prototype of a large-scale search engine which makes heavy use of the structure present in hypertext and looks at the problem of how to effectively deal with uncontrolled hypertext collections where anyone can publish anything they want.
The PageRank Citation Ranking : Bringing Order to the Web
12,645 Citations1999Lawrence M. Page, Sergey Brin +2 more
This paper describes PageRank, a mathod for rating Web pages objectively and mechanically, effectively measuring the human interest and attention devoted to them, and shows how to efficiently compute PageRank for large numbers of pages.
Journal of the ACMAuthoritative sources in a hyperlinked environment
9,060 Citations1999Jon Kleinberg
This work proposes and test an algorithmic formulation of the notion of authority, based on the relationship between a set of relevant authoritative pages and the set of “hub pages” that join them together in the link structure, and has connections to the eigenvectors of certain matrices associated with the link graph.
On power-law relationships of the Internet topology
4,222 Citations1999Michalis Faloutsos, Petros Faloutsos +1 more
These power-laws hold for three snapshots of the Internet, between November 1997 and December 1998, despite a 45% growth of its size during that period, and can be used to generate and select realistic topologies for simulation purposes.
Computer NetworksGraph structure in the Web
2,760 Citations2000Andrei Broder, Ravi Kumar +6 more
The study of the web as a graph yields valuable insight into web algorithms for crawling, searching and community discovery, and the sociological phenomena which characterize its evolution.
Physics TodayLinked: The New Science of Networks
2,330 Citations2003Albert-Ĺaszló Barabási, Maximino Aldana-Gonzalez
An ink jet comprises an elastic tubular member characterized by piezoelectric properties that is terminated in an orifice adapted to pass droplets of ink when the chamber formed within the tubular members is reduced in size.
Princeton University Press eBooksIntroduction to the Numerical Solution of Markov Chains
1,745 Citations1995William J. Stewart
Topic-sensitive PageRank
1,524 Citations2002Taher H. Haveliwala
A set of PageRank vectors are proposed, biased using a set of representative topics, to capture more accurately the notion of importance with respect to a particular topic, and are shown to generate more accurate rankings than with a single, generic PageRank vector.
Internet MathematicsDeeper Inside PageRank
908 Citations2004Amy N. Langville, Carl D. Meyer
A comprehensive survey of all issues associated with PageRank, covering the basic PageRank model, available and recommended solution methods, storage issues, existence, uniqueness, and convergence properties, possible alterations to the basic model, and suggested alternatives to the traditional solution methods.
SIAM ReviewMatrices, Vector Spaces, and Information Retrieval
692 Citations1999Michael W. Berry, Zlatko Drmač +1 more
The purpose of this paper is to show how fundamental mathematical concepts from linear algebra can be used to manage and index large text collections.
ACM SIGIR ForumImproved Algorithms for Topic Distillation in a Hyperlinked Environment
677 Citations2017Krishna Bharat, Monika Henzinger
This paper addresses the problem of topic distillation on the World Wide Web, namely, given a typical user query to find quality documents related to the query topic, by augmenting a previous connectivity analysis based algorithm with content analysis.
Behavior Research Methods, Instruments, & ComputersImproving the retrieval of information from external sources
576 Citations1991Susan Dumais
A statistical method is described called latent semantic indexing, which models the implicit higher order structure in the association of words and objects and improves retrieval performance by up to 30%.
ACM Transactions on Internet TechnologyInside PageRank
535 Citations2005Monica Bianchini, Marco Gori +1 more
A circuit analysis is introduced that allows to understand the distribution of the page score, the way different Web communities interact each other, the role of dangling pages (pages with no outlinks), and the secrets for promotion of Web pages.
Computer NetworksThe stochastic approach for link-structure analysis (SALSA) and the TKC effect
480 Citations2000Ronny Lempel, Shlomo Moran
SALSA, a new stochastic approach for link structure analysis, which examines random walks on graphs derived from the link structure, is presented and it is proved that SALSA is equivalent to a weighted in-degree analysis of the link-structure of World Wide Web subgraphs, making it computationally more efficient than the mutual reinforcement approach.
Extrapolation methods for accelerating PageRank computations
414 Citations2003Sepandar Kamvar, Taher H. Haveliwala +2 more
In Quadratic Extrapolation, the first eigenvalue of a Markov matrix is known to be 1 to compute the nonprincipal eigenvectors using successive iterates of the Power Method, a fast method for determining the dominant eigenvector of a matrix that is too large for standard fast methods to be practical.
The Intelligent surfer: Probabilistic Combination of Link and Content Information in PageRank
364 Citations2001Matthew Richardson, Pedro Domingos
Experiments indicate that the proposed improves PageRank by using a more intelligent surfer, one that is guided by a probabilistic model of the relevance of a page to a query, significantly outperforms PageRank in the (human-rated) quality of the pages returned, while remaining efficient enough to be used in today's large search engines.
Exploiting the Block Structure of the Web for Computing PageRank
316 Citations2003Sepandar Kamvar, Taher H. Haveliwala +2 more
Efficient Computation of PageRank
294 Citations1999Taher H. Haveliwala
It is shown that PageRank can be computed for very large subgraphs of the web (up to hundreds of millions of nodes) on machines with limited main memory.
Stable algorithms for link analysis
290 Citations2001Andrew Y. Ng, Alice X. Zheng +1 more
The analysis is extended and it is shown how it gives insight into ways of designing stable link analysis methods and motivates two new algorithms, whose performance is studied empirically using citation data and web hyperlink data.
Linear Algebra and its ApplicationsAdaptive methods for the computation of PageRank
278 Citations2004Sepandar Kamvar, Taher H. Haveliwala +1 more
A simple algorithm is devised to speed up the computation of PageRank, in which the PageRank of pages that have converged are not recomputed at each iteration after convergence.
The Second Eigenvalue of the Google Matrix
262 Citations2003Taher H. Haveliwala, Sepandar Kamvar
Analysis of the modulus of the second eigenvalue for the web hyperlink matrix used by Google for computing PageRank has implications for the convergence rate of the standard PageRank algorithm as the web scales, for the stability of PageRank to perturbations to the link structure of the web, and for the design of algorithms to speed up PageRank.
Learning to Probabilistically Identify Authoritative Documents
252 Citations2000David Cohn, Huan Chang
A model of document citation that learns to identify hubs and authorities in a set of linked documents, such as pages retrieved from the world wide web, or papers retrieved from a research paper archive, provides probabilistic estimates that have clear semantics.
Finding authorities and hubs from link structures on the World Wide Web
228 Citations2001Allan Borodin, Gareth O. Roberts +2 more
A comparative study of hypertext link analysis algorithms is undertaken, guided by some experimental queries, and some formal criteria for evaluating and comparing linkAnalysis algorithms are proposed.
Link analysis, eigenvectors and stability
203 Citations2001Andrew Y. Ng, Alice X. Zheng +1 more
This paper addresses the question of when HITS and PageRank can be expected to give stable rankings under small perturbations to the hyperlink patterns, using tools from matrix perturbation theory and Markov chain theory.
Computer Networks and ISDN SystemsThe quest for correct information on the Web: hyper search engines
192 Citations1997Massimo Marchiori
This paper presents a novel method to extract from a web object its “hyper” informative content, in contrast with current search engines, which only deal with the “textual’ informative content.
PageRank Computation and the Structure of the Web: Experiments and Algorithms
187 Citations2002Arvind Arasu, Jasmine Novak +2 more
Some computational experiments carried out with variants of the “PageRank” model due to Page et al. are described, with particular reference to the small and large scale structure of the Web.
Journal of the American Society for Information Science and TechnologyMining longitudinal web queries: Trends and patterns
175 Citations2003Peiling Wang, Michael W. Berry +1 more
The purpose of the study is to understand Web users' query behavior, to identify problems encountered by these Web users, and to develop appropriate techniques for optimization of query analysis and mining.
PageRank, HITS and a unified framework for link analysis
165 Citations2002Chris Ding, Xiaofeng He +3 more
This work proves that rankings produced by PageRank and HITS are both highly correlated with the ranking by in-degree and out-degree.
Lecture notes in computer scienceUsing PageRank to Characterize Web Structure
164 Citations2002Gopal Pandurangan, Prabhakar Raghavan +1 more
Computer NetworksWhat is this page known for? Computing Web page reputations
125 Citations2000Davood Rafiei, Alberto O. Mendelzon
A search process where the input is the URL of a page, and the output is a ranked set of topics on which the page has a reputation, and several algorithmic formulations of the notion of reputation are proposed.
SIAM Journal on Scientific ComputingAuthority Rankings from HITS, PageRank, and SALSA: Existence, Uniqueness, and Effect of Initialization
118 Citations2006Ayman Farahat, Thomas LoFaro +3 more
It is proved that Exponentiated Input to HITS returns a unique ranking, provided that the network is weakly connected, and it is shown that SALSA can give inconsistent hub and authority weights, due to nonuniqueness.
Computer NetworksSearchPad: explicit capture of search context to support Web search
108 Citations2000Krishna Bharat
It was discovered that the ability to maintain search context explicitly seems to affect the way people search, and an efficient implementation of this idea deployed on four search engines: AltaVista, Excite, Google and Hotbot is described.
SIAM Journal on Scientific ComputingA Reordering for the PageRank Problem
103 Citations2006Amy N. Langville, Carl D. Meyer
Results of an experimental comparison are presented, which demonstrate that the reordered PageRank algorithm can provide a speedup of as much as a factor of 6.
SIAM ReviewLink Analysis: Hubs and Authorities on the World Wide Web
102 Citations2004Chris Ding, Hongyuan Zha +3 more
This paper gives a detailed analysis of the HITS algorithm through a unique combination of probabilistic analysis and matrix algebra and shows that to first-order approximation, the ranking given by the H ITS algorithm is the same as the ranking by counting inbound and outbound hyperlinks.
Modifications of Kleinberg's HITS algorithm using matrix exponentiation and web log records
74 Citations2001Joel C. Miller, Gregory Rae +4 more
Two modifications to the adjacency matrix input to the HITS algorithm are presented, which weights links according to how often they were followed by users in a given time period and incorporates user feedback without requiring direct user querying.
A new paradigm for ranking pages on the world wide web
74 Citations2003John A. Tomlin
This paper describes a new paradigm for modeling traffic levels on the world wide web using a method of entropy maximization, and specifically applies the primal and dual solutions of this model to the (static) ranking of web sites.
SIAM Journal on Scientific ComputingComparison of Partitioning Techniques for Two-Level Iterative Solvers on Large, Sparse Markov Chains
72 Citations2000Tuǧrul Dayar, William J. Stewart
There is need for further research in this area, specifically to aid in the understanding of the effects of the degree of coupling of NCD Markov chains and their nonzero structure on the convergence characteristics and space requirements of iterative solvers.
Computer NetworksAn efficient algorithm to rank Web resources
59 Citations2000Dell Zhang, Yisheng Dong
A user's Web surfing action is abstracted as a Markov model and a new rank algorithm is proposed, which synthesizes the relevance, authority, integrativity and novelty of each Web resource and can be computed efficiently through solving a group of linear equations.
Adaptive ranking of web pages
50 Citations2003Ah Chung Tsoi, Gianni Morini +3 more
It is demonstrated experimentally on a relatively large web data set, viz., the WT10G, that it is possible to modify the PageRanks of the web pages through the proposed method using a set of linear constraints.
INFORMS Journal on ComputingNumerical Experiments with Iteration and Aggregation for Markov Chains
44 Citations1992William J. Stewart, Wei Biao Wu
An iterative aggregation/disaggregation method for computing the stationary probability vector of a nearly completely decomposable Markov chain with results that are applied to three modeling examples that have been used in the analysis of computer/communication systems.
SIAM Journal on Scientific and Statistical ComputingImproving the Accuracy of Inverse Iteration
42 Citations1992Elizabeth R. Jessup, Ilse C. F. Ipsen
A statistical analysis and the results of numerical experiments are presented to show that the numerical accuracy of this new implementation of TINVIT is competitive with that of the implementations of the divide-and-conquer and QL methods.
Computer NetworksThe Term Vector Database: fast access to indexing terms for Web pages
39 Citations2000Raymie Stata, Krishna Bharat +1 more
The Term Vector Database is a database that provides term vector information for large numbers of pages (hundreds of millions), enabling a large class of applications that would be impractical without such a database.
ACM Transactions on Information SystemsWhen experts agree
36 Citations2002Krishna Bharat, George A. Mihaila
This paper proposes a novel ranking scheme for popular topics that places the most authoritative pages on the query topic at the top of the ranking, and presents a prototype search engine that implements the scheme and discusses its performance.
Application of threshold partitioning of sparse matrices to Markov chains
33 Citations2002Hyeung‐Sik Choi, Daniel B. Szyld
Three algorithms which permute and partition a sparse matrix are presented as tools for the improved solution of Markov chain problems and if the partition obtained from the ordering algorithm is used as an aggregation scheme, an iterative aggregation method performs better with this partition than with others found in the literature.
Information Processing & ManagementLevel search schemes for information filtering and retrieval
20 Citations2001Xiaoyan Zhang, Michael W. Berry +1 more
Information filtering using level search techniques can reduce the SVD computation cost for LSI, and enhancement of level search can be based on a pruning scheme which deleting terms connected to only one document from the query-specific submatrix.
Prensas Universitarias de Zaragoza eBooksExperimental study of parallel iterative solutions of Markov chains with block partitions
7 Citations1999Violeta Migallón, José Penadés +1 more
This research is supported by the Spanish CICYT grant PB96-1054-CV02-1, National Science Foundation grants INT-5 and DMS-9625865.