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. 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 context on the World Wide Web. The central issue we address within our framework is the distillation of broad search topics, through the discovery of “authorative” 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 heuristrics for link-based analysis.

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Gustavo O. Arocena , Alberto O. Mendelzon , George A. Mihaila, Applications of a Web query language, Selected papers from the sixth international conference on World Wide Web, p.1305-1316, September 1997, Santa Clara, California, United States
	2	Rob Barrett , Paul P. Maglio , Daniel C. Kellem, How to personalize the Web, Proceedings of the SIGCHI conference on Human factors in computing systems, p.75-82, March 22-27, 1997, Atlanta, Georgia, United States  [doi>10.1145/258549.258595]
	3	BERMAN, O., HODGSON,M.J.,AND KRASS, D. 1995. Flow-interception problems. In Facility Location: A Survey of Applications and Methods, Z. Drezner, ed. Springer-Verlag, New York.
	4	Tim Berners-Lee , Robert Cailliau , Ari Luotonen , Henrik Frystyk Nielsen , Arthur Secret, The World-Wide Web, Communications of the ACM, v.37 n.8, p.76-82, Aug. 1994  [doi>10.1145/179606.179671]
	5	Krishna Bharat , Andrei Broder , Monika Henzinger , Puneet Kumar , Suresh Venkatasubramanian, The connectivity server: fast access to linkage information on the Web, Proceedings of the seventh international conference on World Wide Web 7, p.469-477, April 1998, Brisbane, Australia
	6	Krishna Bharat , Monika R. Henzinger, Improved algorithms for topic distillation in a hyperlinked environment, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.104-111, August 24-28, 1998, Melbourne, Australia  [doi>10.1145/290941.290972]
	7	Rodrigo A. Botafogo , Ehud Rivlin , Ben Shneiderman, Structural analysis of hypertexts: identifying hierarchies and useful metrics, ACM Transactions on Information Systems (TOIS), v.10 n.2, p.142-180, April 1992  [doi>10.1145/146802.146826]
	8	Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Proceedings of the seventh international conference on World Wide Web 7, p.107-117, April 1998, Brisbane, Australia
	9	S. Jeromy Carrière , Rick Kazman, WebQuery: searching and visualizing the Web through connectivity, Selected papers from the sixth international conference on World Wide Web, p.1257-1267, September 1997, Santa Clara, California, United States
	10	CHAKRABARTI, S., DOM, B., GIBSON, D., KUMAR,S.R.,RAGHAVAN, P., RAJAGOPALAN, S., AND TOMKINS, A. 1998. Experiments in topic distillation. In Proceedings of the ACM SIGIR Workshop on Hypertext Information Retrieval on the Web (Melbourne, Australia). ACM, New York.
	11	Soumen Chakrabarti , Byron Dom , Prabhakar Raghavan , Sridhar Rajagopalan , David Gibson , Jon Kleinberg, Automatic resource compilation by analyzing hyperlink structure and associated text, Proceedings of the seventh international conference on World Wide Web 7, p.65-74, April 1998, Brisbane, Australia
	12	CHUNG, F. R. K. 1997. Spectral Graph Theory. AMS Press, Providence, R.I.
	13	CHEKURI, C., GOLDWASSER, M., RAGHAVAN, P., AND UPFAL, E. 1997. Web search using automated classification. In Proceedings of the 6th International World Wide Web Conference (Santa Clara, Calif., Apr. 7-11).
	14	Douglass R. Cutting , David R. Karger , Jan O. Pedersen , John W. Tukey, Scatter/Gather: a cluster-based approach to browsing large document collections, Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval, p.318-329, June 21-24, 1992, Copenhagen, Denmark  [doi>10.1145/133160.133214]
	15	DE SOLLA PRICE, D. 1981. The analysis of square matrices of scientometric transactions. Sciento-metrics 3 55-63.
	16	DEERWESTER, S., DUMAIS, S., LANDAUER, T., FURNAS, G., AND HARSHMAN, R. 1990. Indexing by latent semantic analysis. J. Amer. Soc. Info. Sci. 41, 391-407.
	17	DIGITAL EQUIPMENT CORPORATION. AltaVista search engine, http://altavista.digital.com/.
	18	DONATH,W.E.,AND HOFFMAN, A. J. 1973. Lower bounds for the partitioning of graphs. IBM J. Res. Develop. 17.
	19	Patrick Doreian, Measuring the relative standing of disciplinary journals, Information Processing and Management: an International Journal, v.24 n.1, p.45-56, January 1988  [doi>10.1016/0306-4573(88)90077-5 ]
	20	Patrick Doreian, A measure of standing for citation networks within a wider environment, Information Processing and Management: an International Journal, v.30 n.1, p.21-31, Jan.-Feb. 1994  [doi>10.1016/0306-4573(94)90021-3 ]
	21	L. Egghe, Mathematical relations between impact factors and average number of citations, Information Processing and Management: an International Journal, v.24 n.5, p.567-576, 1988  [doi>10.1016/0306-4573(88)90026-X ]
	22	EGGHE, L., AND ROUSSEAU, R. 1990. Introduction to Informetrics, Elsevier, North-Holland, Am-sterdam, The Netherlands.
	23	FIELDER, M. 1973. Algebraic connectivity of graphs. Czech. Math. J. 23, 298-305.
	24	Alan Frieze , Ravi Kannan , Santosh Vempala, Fast Monte-Carlo Algorithms for finding low-rank approximations, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.370, November 08-11, 1998
	25	Mark,E. Frisse, Searching for information in a hypertext medical handbook, Communications of the ACM, v.31 n.7, p.880-886, July 1988  [doi>10.1145/48511.48518]
	26	GARFIELD, E. 1972. Citation analysis as a tool in journal evaluation. Science 178, 471-479.
	27	GELLER, N. 1978. On the citation influence methodology of Pinski and Narin. Inf. Proc. Manage. 14, 93-95.
	28	David Gibson , Jon Kleinberg , Prabhakar Raghavan, Inferring Web communities from link topology, Proceedings of the ninth ACM conference on Hypertext and hypermedia : links, objects, time and space---structure in hypermedia systems: links, objects, time and space---structure in hypermedia systems, p.225-234, June 20-24, 1998, Pittsburgh, Pennsylvania, United States  [doi>10.1145/276627.276652]
	29	David Gibson , Jon M. Kleinberg , Prabhakar Raghavan, Clustering Categorical Data: An Approach Based on Dynamical Systems, Proceedings of the 24rd International Conference on Very Large Data Bases, p.311-322, August 24-27, 1998
	30	GOLUB, G., AND VAN LOAN, C. F. 1989. Matrix Computations. Johns Hopkins University Press, Baltimore, Md.
	31	HOTELLING, H. 1933. Analysis of a complex statistical variable into principal components. J. Educ. Psychol. 24, 417-441.
	32	HUBBELL, C. H. 1965. An input-output approach to clique identification. Sociometry 28, 377-399.
	33	HUBERMAN, B., PIROLLI, P., PITKOW, J., AND LUKOSE, R. 1998. Strong regularities in world wide web surfing. Science, 280.
	34	JOLLIFFE, I. T. 1986. Principal Component Analysis. Springer-Verlag, New York.
	35	KATZ, L. 1953. A new status index derived from sociometric analysis. Psychometrika 18, 39-43.
	36	KESSLER, M. M. 1963. Bibliographic coupling between scientific papers. Amer. Document. 14, 10-25.
	37	LARSON, R. 1996. Bibliometrics of the world wide web: An exploratory analysis of the intellectual structure of cyberspace. In Proceedings of the Annual Meeting of the American Society of Information Science (Baltimore, Md., Oct. 19-24).
	38	LEVINE, J. H. 1979. Joint-space analysis of 'pick-any' data: Analysis of choices from an uncon-strained set of alternatives. Psychometrika, 44, 85-92.
	39	Massimo Marchiori, The quest for correct information on the Web: hyper search engines, Selected papers from the sixth international conference on World Wide Web, p.1225-1235, September 1997, Santa Clara, California, United States
	40	MCBRYAN, O. 1994. GENVL and WWWW: Tools for taming the web. In Proceedings of the 1st International World Wide Web Conference (Geneva, Switzerland, May).
	41	MCCAIN, K. 1986. Co-cited author mapping as a valid representation of intellectual structure. J. Amer. Soc. Info. Sci. 37, 111-122.
	42	NOMA, E. 1982. An improved method for analyzing square scientometric transaction matrices. Scientometrics 4, 297-316.
	43	NOMA, E. 1984. Co-citation analysis and the invisible college. J. Amer. Soc. Info. Sci. 35, 29-33.
	44	Christos H. Papadimitriou , Hisao Tamaki , Prabhakar Raghavan , Santosh Vempala, Latent semantic indexing: a probabilistic analysis, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.159-168, June 01-04, 1998, Seattle, Washington, United States  [doi>10.1145/275487.275505]
	45	PINSKI, G., AND NARIN, F. 1976. Citation influence for journal aggregates of scientific publications: Theory, with application to the literature of physics. Inf. Proc. Manage. 12, 297-312.
	46	Peter Pirolli , James Pitkow , Ramana Rao, Silk from a sow's ear: extracting usable structures from the Web, Proceedings of the SIGCHI conference on Human factors in computing systems: common ground, p.118-125, April 13-18, 1996, Vancouver, British Columbia, Canada  [doi>10.1145/238386.238450]
	47	James Pitkow , Peter Pirolli, Life, death, and lawfulness on the electronic frontier, Proceedings of the SIGCHI conference on Human factors in computing systems, p.383-390, March 22-27, 1997, Atlanta, Georgia, United States  [doi>10.1145/258549.258805]
	48	Gerald Salton, Automatic text processing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
	49	SHAW, W. M. 1991. Subject and citation indexing. Part I: The clustering structure of composite representations in the cystic fibrosis document collection. J. Amer. Soc. Info. Sci. 42, 669-675.
	50	SHAW, W. M. 1991. Subject and citation indexing. Part II: The optimal, cluster-based retrieval performance of composite representations. J. Amer. Soc. Info. Sci. 42, 676-684.
	51	SMALL, H. 1973. Co-citation in the scientific literature: A new measure of the relationship between two documents. J. Amer. Soc. Info. Sci. 24, 265-269.
	52	Henry Small, The synthesis of specialty narratives from co-citation clusters, Journal of the American Society for Information Science, v.37 n.3, p.97-110, May 1986  [doi>10.1002/(SICI)1097-4571(198605)37:3<97::AID-ASI1>3.0.CO;2-K]
	53	SMALL, H., AND GRIFFITH, B. C. 1974. The structure of the scientific literatures I. Identifying and graphing specialties. Science Studies 4, 17-40.
	54	Ellen Spertus, ParaSite: mining structural information on the Web, Selected papers from the sixth international conference on World Wide Web, p.1205-1215, September 1997, Santa Clara, California, United States
	55	C. J. Van Rijsbergen, Information Retrieval, Butterworth-Heinemann, Newton, MA, 1979
	56	Ron Weiss , Bienvenido Vélez , Mark A. Sheldon, HyPursuit: a hierarchical network search engine that exploits content-link hypertext clustering, Proceedings of the the seventh ACM conference on Hypertext, p.180-193, March 16-20, 1996, Bethesda, Maryland, United States  [doi>10.1145/234828.234846]
	57	WIRED DIGITAL,INC. Hotbot, http://www.hotbot.com.
	58	YAHOO!CORPORATION Yahoo!, http://www.yahoo.com.