This paper develops a link-based method for discovering authoritative web pages on broad search topics. It constructs focused subgraphs from search results and iteratively computes mutually reinforcing hub and authority weights, relating them to principal eigenvectors. Experiments illustrate applications to topic searches and similar-page queries. The paper also explores multiple authority communities using non-principal eigenvectors, diffusion toward broader topics, connections to bibliometrics and social networks, and user studies of search systems built on extensions of the method.
Free preview text
The first 5 pages, shown as text so search engines and readers can find this document.
Page 1
Authoritative Sources in a Hyperlinked Environment∗
Jon M. Kleinberg †
Abstract
The network structure of a hyperlinked environment can be a rich source of in-
formation about the content of the environment, provided we have effective means for
understanding it. We develop a set of algorithmic tools for extracting information from
the link structures of such environments, and report on experiments that demonstrate
their effectiveness in a variety of contexts on the World Wide Web. The central issue
we address within our framework is the distillation of broad search topics, through
the discovery of “authoritative” information sources on such topics. We propose 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. Our formulation has connections to the eigenvectors
of certain matrices associated with the link graph; these connections in turn motivate
additional heuristics for link-based analysis.
∗Preliminary versions of this paper appear in the Proceedings of the ACM-SIAM Symposium on Discrete
Algorithms, 1998, and as IBM Research Report RJ 10076, May 1997.
†Dept. of Computer Science, Cornell University, Ithaca NY 14853. Email: kleinber@cs.cornell.edu.
This work was performed in large part while on leave at the IBM Almaden Research Center, San Jose CA
95120. The author is currently supported by an Alfred P. Sloan Research Fellowship and by NSF Faculty
Early Career Development Award CCR-9701399.
Page 2
1 Introduction
The network structure of a hyperlinked environment can be a rich source of information
about the content of the environment, provided we have effective means for understanding
it. In this work, we develop a set of algorithmic tools for extracting information from the
link structures of such environments, and report on experiments that demonstrate their
effectiveness in a variety of contexts on the World Wide Web (www) [4]. In particular, we
focus on the use of links for analyzing the collection of pages relevant to a broad search topic,
and for discovering the most “authoritative” pages on such topics.
While our techniques are not specific to the www, we find the problems of search and
structural analysis particularly compelling in the context of this domain. The www is a
hypertext corpus of enormous complexity, and it continues to expand at a phenomenal rate.
Moreover, it can be viewed as an intricate form of populist hypermedia, in which millions
of on-line participants, with diverse and often conflicting goals, are continuously creating
hyperlinked content. Thus, while individuals can impose order at an extremely local level,
its global organization is utterly unplanned — high-level structure can emerge only through
a posteriori analysis.
Our work originates in the problem of searching on the www, which we could define
roughly as the process of discovering pages that are relevant to a given query. The quality of
a search method necessarily requires human evaluation, due to the subjectivity inherent in
notions such as relevance. We begin from the observation that improving the quality of search
methods on the www is, at the present time, a rich and interesting problem that is in many
ways orthogonal to concerns of algorithmic efficiency and storage. In particular, consider
that current search engines typically index a sizable portion of the www and respond on
the order of seconds. Although there would be considerable utility in a search tool with a
longer response time, provided that the results were of significantly greater value to a user,
it has typically been very hard to say what such a search tool should be computing with this
extra time. Clearly we are lacking objective functions that are both concretely defined and
correspond to human notions of quality.
Queries and Authoritative Sources. We view searching as beginning from a user-
supplied query. It seems best not to take too unified a view of the notion of a query; there
is more than one type of query, and the handling of each may require different techniques.
Consider, for example, the following types of queries.
• Specific queries. E.g., “Does Netscape support the JDK 1.1 code-signing API?”
• Broad-topic queries. E.g., “Find information about the Java programming language.”
• Similar-page queries. E.g., “Find pages ‘similar’ to java.sun.com.”
Concentrating on just the first two types of queries for now, we see that they present very
different sorts of obstacles. The difficulty in handling specific queries is centered, roughly,
around what could be called the Scarcity Problem: there are very few pages that contain the
1
Page 3
required information, and it is often difficult to determine the identity of these pages.
For broad-topic queries, on the other hand, one expects to find many thousand relevant
pages on the www; such a set of pages might be generated by variants of term-matching
(e.g. one enters a string such as “Gates,” “search engines,” or “censorship” into a search
engine such as AltaVista [17]), or by more sophisticated means. Thus, there is not an
issue of scarcity here. Instead, the fundamental difficulty lies in what could be called the
Abundance Problem: The number of pages that could reasonably be returned as relevant is
far too large for a human user to digest. To provide effective search methods under these
conditions, one needs a way to filter, from among a huge collection of relevant pages, a small
set of the most “authoritative” or “definitive” ones.
This notion of authority, relative to a broad-topic query, serves as a central focus in our
work. One of the fundamental obstacles we face in addressing this issue is that of accurately
modeling authority in the context of a particular query topic. Given a particular page, how
do we tell whether it is authoritative?
It is useful to discuss some of the complications that arise here. First, consider the natural
goal of reporting www.harvard.edu, the home page of Harvard University, as one of the most
authoritative pages for the query "Harvard". Unfortunately, there are over a million pages
on the www that use the term “Harvard,” and www.harvard.edu is not the one that uses
the term most often, or most prominently, or in any other way that would favor it under
a text-based ranking function. Indeed, one suspects that there is no purely endogenous
measure of the page that would allow one to properly assess its authority. Second, consider
the problem of finding the home pages of the main www search engines. One could begin
from the query "search engines", but there is an immediate difficulty in the fact that
many of the natural authorities (Yahoo!, Excite, AltaVista) do not use the term on their
pages. This is a fundamental and recurring phenomenon — as another example, there is
no reason to expect the home pages of Honda or Toyota to contain the term “automobile
manufacturers.”
Analysis of the Link Structure. Analyzing the hyperlink structure among www pages
gives us a way to address many of the difficulties discussed above. Hyperlinks encode a
considerable amount of latent human judgment, and we claim that this type of judgment
is precisely what is needed to formulate a notion of authority. Specifically, the creation of
a link on the www represents a concrete indication of the following type of judgment: the
creator of page p, by including a link to page q, has in some measure conferred authority on
q. Moreover, links afford us the opportunity to find potential authorities purely through the
pages that point to them; this offers a way to circumvent the problem, discussed above, that
many prominent pages are not sufficiently self-descriptive.
Of course, there are a number of potential pitfalls in the application of links for such
a purpose. First of all, links are created for a wide variety of reasons, many of which
2
Page 4
have nothing to do with the conferral of authority. For example, a large number of links
are created primarily for navigational purposes (“Click here to return to the main menu”);
others represent paid advertisements.
Another issue is the difficulty in finding an appropriate balance between the criteria of
relevance and popularity, each of which contributes to our intuitive notion of authority. It
is instructive to consider the serious problems inherent in the following simple heuristic for
locating authoritative pages: Of all pages containing the query string, return those with the
greatest number of in-links. We have already argued that for a great many queries ("search
engines", "automobile manufacturers", . . . ), a number of the most authoritative pages
do not contain the associated query string. Conversely, this heuristic would consider a univer-
sally popular page such as www.yahoo.com or www.netscape.com to be highly authoritative
with respect to any query string that it contained.
In this work, we propose a link-based model for the conferral of authority, and show how
it leads to a method that consistently identifies relevant, authoritative www pages for broad
search topics. Our model is based on the relationship that exists between the authorities for
a topic and those pages that link to many related authorities — we refer to pages of this
latter type as hubs. We observe that a certain natural type of equilibrium exists between
hubs and authorities in the graph defined by the link structure, and we exploit this to develop
an algorithm that identifies both types of pages simultaneously. The algorithm operates on
focused subgraphs of the www that we construct from the output of a text-based www
search engine; our technique for constructing such subgraphs is designed to produce small
collections of pages likely to contain the most authoritative pages for a given topic.
Overview. Our approach to discovering authoritative www sources is meant to have a
global nature: We wish to identify the most central pages for broad search topics in the
context of the www as a whole. Global approaches involve basic problems of representing
and filtering large volumes of information, since the entire set of pages relevant to a broad-
topic query can have a size in the millions. This is in contrast to local approaches that seek
to understand the interconnections among the set of www pages belonging to a single logical
site or intranet; in such cases the amount of data is much smaller, and often a different set
of considerations dominates.
It is also important to note the sense in which our main concerns are fundamentally
different from problems of clustering. Clustering addresses the issue of dissecting a hetero-
geneous population into sub-populations that are in some way more cohesive; in the context
of the www, this may involve distinguishing pages related to different meanings or senses
of a query term. Thus, clustering is intrinsically different from the issue of distilling broad
topics via the discovery of authorities, although a subsequent section will indicate some con-
nections. For even if we were able perfectly to dissect the multiple senses of an ambiguous
query term (e.g. “Windows” or “Gates”), we would still be left with the same underlying
3
Page 5
problem of representing and filtering the vast number of pages that are relevant to each of
the main senses of the query term.
The paper is organized as follows. Section 2 discusses the method by which we construct
a focused subgraph of the www with respect to a broad search topic, producing a set of
relevant pages rich in candidate authorities. Sections 3 and 4 discuss our main algorithm
for identifying hubs and authorities in such a subgraph, and some of the applications of this
algorithm. Section 5 discusses the connections with related work in the areas of www search,
bibliometrics, and the study of social networks. Section 6 describes how an extension of our
basic algorithm produces multiple collections of hubs and authorities within a common link
structure. Finally, Section 7 investigates the question of how “broad” a topic must be in
order for our techniques to be effective, and Section 8 surveys some work that has been done
on the evaluation of the method presented here.
2 Constructing a Focused Subgraph of the WWW
We can view any collection V of hyperlinked pages as a directed graph G = (V, E): the
nodes correspond to the pages, and a directed edge (p, q) ∈ E indicates the presence of a
link from p to q. We say that the out-degree of a node p is the number of nodes it has links
to, and the in-degree of p is is the number of nodes that have links to it. From a graph G,
we can isolate small regions, or subgraphs, in the following way. If W ⊆ V is a subset of the
pages, we use G[W ] to denote the graph induced on W : its nodes are the pages in W , and
its edges correspond to all the links between pages in W .
Suppose we are given a broad-topic query, specified by a query string σ. We wish to de-
termine authoritative pages by an analysis of the link structure; but first we must determine
the subgraph of the www on which our algorithm will operate. Our goal here is to focus the
computational effort on relevant pages. Thus, for example, we could restrict the analysis to
the set Qσ of all pages containing the query string; but this has two significant drawbacks.
First, this set may contain well over a million pages, and hence entail a considerable compu-
tational cost; and second, we have already noted that some or most of the best authorities
may not belong to this set.
Ideally, we would like to focus on a collection Sσ of pages with the following properties.
(i) Sσ is relatively small.
(ii) Sσ is rich in relevant pages.
(iii) Sσ contains most (or many) of the strongest authorities.
By keeping Sσ small, we are able to afford the computational cost of applying non-trivial
algorithms; by ensuring it is rich in relevant pages we make it easier to find good authorities,
as these are likely to be heavily referenced within Sσ.
How can we find such a collection of pages? For a parameter t (typically set to about
200), we first collect the t highest-ranked pages for the query σ from a text-based search
4
Authoritative Sources in a Hyperlinked Environment: summary, contents and background
This guide helps you understand the scope of Authoritative Sources in a Hyperlinked Environment before or alongside reading the original document. It is based on the catalogue record, credited creator, source, classification and topics shown on this page. It does not replace the original work and does not invent claims about passages that Doxxly cannot verify.
Summary and overview
Authoritative Sources in a Hyperlinked Environment is a 34-page documentcredited to Kaya Q. Underhill. This paper develops a link-based method for discovering authoritative web pages on broad search topics. It constructs focused subgraphs from search results and iteratively computes mutually reinforcing hub and authority weights, relating them to principal eigenvectors. Experiments illustrate applications to topic searches and similar-page queries. The paper also explores multiple authority communities using non-principal eigenvectors, diffusion toward broader topics, connections to bibliometrics and social networks, and user studies of search systems built on extensions of the method. It appears in the Science & Engineering collection, which groups it with other material that readers may use for comparison and further study.
The item can be approached in several ways. A reader looking for a quick orientation can begin with the free five-page preview, inspect the page structure and use the metadata to judge relevance. Someone undertaking deeper research can work through the complete file, search its indexed text, record useful page references and compare its treatment of Web search, Hyperlink analysis, Hubs and authorities, Information retrieval, Eigenvector algorithms, Graph analysis, Bibliometrics, Web communities with the related resources linked below.
Rather than reducing the work to a single claim, this page treats it as a source that should be read in context. The title, creator, publication source, licence and format all help explain what kind of evidence it may offer. Readers should distinguish the original author's statements from Doxxly's catalogue description, and should cite the original edition when using the material in academic, professional or published work.
Key topics and reader takeaways
The catalogue connects this document with Web search, Hyperlink analysis, Hubs and authorities, Information retrieval, Eigenvector algorithms, Graph analysis, Bibliometrics, Web communities. These terms offer practical entry points rather than a substitute for close reading. Start by identifying the definitions, examples, arguments, tables or visual explanations attached to each topic. Then note where the creator draws connections, makes distinctions or moves from background material to a conclusion, recommendation, calculation or narrative development.
A useful reading method is to separate description from interpretation. First record what the item actually presents: names, headings, figures, formulas, quotations or stated propositions. Next consider why those details matter within the whole work. Finally compare them with another source from the same subject area. This process helps turn a long digital file into evidence that can be evaluated rather than merely skimmed.
Table of contents and reading guide
The following is an editorial content guide based on the verified catalogue topics. It is not represented as the original author's formal table of contents. Use it to organise notes while moving through the 34 pages in the player.
Part 1
Web search
Use this section of the reading guide to identify how Web search appears in Authoritative Sources in a Hyperlinked Environment, note important terms, and connect the subject to the wider purpose of the work.
Part 2
Hyperlink analysis
Use this section of the reading guide to identify how Hyperlink analysis appears in Authoritative Sources in a Hyperlinked Environment, note important terms, and connect the subject to the wider purpose of the work.
Part 3
Hubs and authorities
Use this section of the reading guide to identify how Hubs and authorities appears in Authoritative Sources in a Hyperlinked Environment, note important terms, and connect the subject to the wider purpose of the work.
Part 4
Information retrieval
Use this section of the reading guide to identify how Information retrieval appears in Authoritative Sources in a Hyperlinked Environment, note important terms, and connect the subject to the wider purpose of the work.
Part 5
Eigenvector algorithms
Use this section of the reading guide to identify how Eigenvector algorithms appears in Authoritative Sources in a Hyperlinked Environment, note important terms, and connect the subject to the wider purpose of the work.
Part 6
Graph analysis
Use this section of the reading guide to identify how Graph analysis appears in Authoritative Sources in a Hyperlinked Environment, note important terms, and connect the subject to the wider purpose of the work.
Part 7
Bibliometrics
Use this section of the reading guide to identify how Bibliometrics appears in Authoritative Sources in a Hyperlinked Environment, note important terms, and connect the subject to the wider purpose of the work.
Part 8
Web communities
Use this section of the reading guide to identify how Web communities appears in Authoritative Sources in a Hyperlinked Environment, note important terms, and connect the subject to the wider purpose of the work.
When a heading in the original differs from this guide, follow the original heading in your citation. Page numbers can also vary between editions. Doxxly's direct page field is useful for navigation, but formal references should include the title, creator, source and edition details available in the file itself.
About Kaya Q. Underhill
Doxxly credits Kaya Q. Underhill as the author or creator of Authoritative Sources in a Hyperlinked Environment. This page does not add an unverified biography, job title or institutional affiliation. The attribution is preserved so readers can distinguish the creator from the hosting library and follow the original record when an external author link is available.
Author context matters because a work reflects a particular purpose, audience and point of view. Before relying on the material, consider what the creator set out to explain, when the source was produced and whether later research or revised guidance should also be consulted. For literature and philosophy, compare translations and editions; for technical material, check whether a newer version has superseded the one shown here.
About the source organisation
The recorded source for this item is cs.cornell.edu. Doxxly provides access and discovery tools but does not claim to be the original publisher unless explicitly stated. Source links, creator attribution and the recorded Publicly available file collected for editorial review licence are displayed to help readers assess provenance and permitted use.
Provenance is especially important for reports, standards, presentations and working spreadsheets. Check the original source for amendments, supporting files and current policy. A trustworthy research workflow keeps the source URL with any notes or downloaded copy, verifies important figures against the original, and avoids treating an archived document as automatically current.
Begin with the title and opening pages, then use the guide above to decide whether to read sequentially or move to a particular topic. The Doxxly player provides previous and next navigation, a direct page field, zoom steps, fit-to-width and fit-to-page modes, rotation and fullscreen. These controls are useful when a page contains small type, a wide table, an image, a scanned layout or a dense sequence of notes.
The first five pages are open to every visitor. A plan unlocks the complete item and full-document search. Search is best used for distinctive names, technical terms or short phrases; broad words can produce too many possible contexts. When you find a useful passage, read the surrounding pages so that a sentence, chart or formula is not separated from its explanation.
If downloading is enabled, members can obtain the original PDF file. Keep the original format when formulas, slide sequencing, pagination or layout carries meaning. Respect the Publicly available file collected for editorial review terms displayed on this page, and use the rights-report link if you believe the attribution or availability needs review.
Research questions to consider
As you read Authoritative Sources in a Hyperlinked Environment, ask which audience the creator addresses, what problem or idea organises the work, what evidence is presented, and which assumptions remain unstated. Note whether important terms are defined consistently and whether examples represent a broader pattern or a narrow case. For quantitative material, record units, time periods, formulas and data sources. For interpretive material, separate the creator's language from your own summary.
A second set of questions concerns relevance today. Which parts remain durable, which depend on their historical or institutional setting, and what would need confirmation from a newer source? Following the tags and the Science & Engineering collection can reveal useful comparisons. Agreement between sources can strengthen confidence, while disagreement can point to changing definitions, methods, evidence or priorities.
Finally, decide what you need from the item: background knowledge, a quotation, a worked example, a model, a visual explanation or a starting bibliography. That purpose should guide the depth of reading and the notes you keep. Doxxly helps locate and navigate the source; careful interpretation remains the reader's responsibility.