9/22/97 - Jon Kleinberg
Cornell University
A Spectral Method for Searching in Hyperlinked Environments

Current search tools for hyperlinked environments such as the World Wide Web make little or no use of the underlying link structure. At the same time, such link structures arise from the combined efforts of millions of individuals, and thus contain huge amounts of latent human annotation; what has been missing is a set of algorithmic techniques for making effective use of this implicit structure contained in the links. In this work, we discuss a new method for automatically extracting certain types of information about a hypermedia environment from its link structure, and we report on experiments that demonstrate its effectiveness for a variety of search problems on the WWW.

One of the main problems we consider within our framework is that of determining the relative "authority'' of pages in such environments. This issue is central to a number of basic hypertext search tasks; for example, if the result of a query-based search consists of a large set of relevant pages, one may wish to select a small subset of the most "definitive'' or "authoritative'' pages to present to a user. At the same time, it is clearly difficult to formulate a definition of authority precise enough to be used in such contexts.

We propose and test an algorithmic formulation of the notion of authority, based on a method for locating dense bipartite "communities'' in the link structure. Our formulation has an interesting interpretation in terms of the eigenvectors of certain matrices associated with the link graph; this motivates additional heuristics for clustering and for computing a type of link-based similarity among hyperlinked documents.