Elamur Research
☰
home / papers / 1999 / Authoritative Sources in a Hyperlinked Environment

Authoritative Sources in a Hyperlinked Environment

Written for the Research library (claude-opus-5-5) from the paper text, in our own words: the license "author's copy — read only" does not allow redistributing the text itself. Original — cs.cornell.edu/home/kleinber/auth.pdf

Summary

Kleinberg addresses broad-topic web search. Here the main obstacle is not finding relevant pages but the sheer number of them (the Abundance Problem). The best sources also often never use the query term: Yahoo! or AltaVista rarely call themselves "search engines". The paper argues that hyperlinks encode implicit human endorsement, so they can reveal authority that text-based ranking misses.

The method does not index the whole web. It starts from the output of a standard text search engine such as AltaVista and assembles a small, focused subgraph likely to contain the strongest authorities for the query. Within this subgraph it finds two mutually reinforcing kinds of pages:

  • authorities, which are linked to by many good hubs;
  • hubs, which point to many related authorities.

This equilibrium is formalised through eigenvectors of matrices built from the link graph. Additional eigenvectors separate several distinct hub/authority groups that share one link structure. Experiments on the WWW show that the approach reliably surfaces relevant, authoritative pages across many topics. Its importance lies in offering a principled, link-based model of authority, which later systems for compiling resource lists and studying web communities built on.

Key points

  • The paper separates three query types: specific queries (affected by the Scarcity Problem), broad-topic queries (affected by the Abundance Problem) and similar-page queries. Broad-topic queries are the main focus.
  • Simply ranking pages by in-link count fails. Universally popular sites like www.yahoo.com would rank highly for any term they happen to contain, and www.harvard.edu does not stand out by text among the over a million pages mentioning "Harvard".
  • The focused subgraph S_σ is required to be small, rich in relevant pages and to contain many of the strongest authorities. This contrasts with the full set Q_σ of pages containing the query string, which may exceed a million pages and can miss key authorities.
  • The hub/authority model is related to eigenvectors of link-graph matrices. It is explicitly distinguished from clustering, and the paper connects it to bibliometrics and social network analysis.
  • The JACM 46(5), 1999 version was preceded by a SODA 1998 paper and by IBM Research Report RJ 10076, issued in May 1997. Extensions include work by Bharat & Henzinger, whose system used the Connectivity Server over the AltaVista index, and by Chakrabarti et al.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Computing & GPUs

Cited by

130 papers of our library cite it (of the 140673 whose bibliographies we read); 4 of them have a page here, 126 not yet.

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.1145/324133.324140

@article{kleinberg1999authoritative,
  title = {{Authoritative Sources in a Hyperlinked Environment}},
  author = {Kleinberg, Jon M.},
  journal = {Journal of the ACM 46(5)},
  year = {1999},
  doi = {10.1145/324133.324140},
  url = {https://doi.org/10.1145/324133.324140}
}

References

58 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. G.O. Arocena, A.O. Mendelzon, G.A. Mihaila, “Applications of a Web query language,” Proc. 6th International World Wide Web Conference, 1997. find
  2. R. Barrett, P. Maglio, D. Kellem, “How to personalize the Web,” Proc. Conf. on Human Factors in Computing Systems, 1997. find
  3. O. Berman, M.J. Hodgson, D. Krass. “Flow-interception problems,” in Facility Location: A Survey of Applications and Methods, Z. Drezner, Ed., Springer 1995. find
  4. T. Berners-Lee, R. Cailliau, A. Luotonen, H.F. Nielsen, A. Secret. “The World-Wide Web,” Communications of the ACM, 37(1994), pp. 76–82. find
  5. K. Bharat, A. Broder, M.R. Henzinger, P. Kumar, S. Venkatasubramanian, “Connectivity Server: Fast Access to Linkage Information on the Web,” Proc. 7th Intl. World Wide Web Conf., 1998. find
  6. K. Bharat, M.R. Henzinger, “Improved algorithms for topic distillation in a hyperlinked environment,” Proc. ACM Conf. Res. and Development in Information Retrieval, 1998. find
  7. R. Botafogo, E. Rivlin, B. Shneiderman, “Structural analysis of hypertext: Identifying hierarchies and useful metrics,” ACM Trans. Inf. Sys., 10(1992), pp. 142–180. find
  8. S. Brin, L. Page, “Anatomy of a Large-Scale Hypertextual Web Search Engine,” Proc. 7th International World Wide Web Conference, 1998. find
  9. J. Carrière, R. Kazman, “WebQuery: Searching and visualizing the Web through connectivity,” Proc. 6th International World Wide Web Conference, 1997. find
  10. S. Chakrabarti, B. Dom, D. Gibson, S.R. Kumar, P. Raghavan, S. Rajagopalan and A. Tomkins, “Experiments in Topic Distillation,” ACM SIGIR Workshop on Hypertext Information Retrieval on the Web, 1998. find
  11. S. Chakrabarti, B. Dom, D. Gibson, J. Kleinberg, P. Raghavan, S. Rajagopalan, “Automatic Resource Compilation by Analyzing Hyperlink Structure and Associated Text,” Proc. 7th International World Wide Web Conference, 1998. find
  12. F.R.K. Chung, Spectral Graph Theory, AMS Press, 1997. find
  13. C. Chekuri, M. Goldwasser, P. Raghavan and E. Upfal “Web search using automated classification,” poster at 6th International World Wide Web Conference, 1997. find
  14. D.R. Cutting, J. Pedersen, D.R. Karger, J.W. Tukey, “Scatter/gather: A cluster-based approach to browsing large document collections,” Proc. ACM Conf. Res. and Development in Information Retrieval, 1992. find
  15. D. de Solla Price, “The analysis of square matrices of scientometric transactions,” Scientometrics, 3(1981), pp. 55–63. find
  16. S. Deerwester, S. Dumais, T. Landauer, G. Furnas, R. Harshman, “Indexing by latent semantic analysis,” J. American Soc. Info. Sci., 41(1990), pp. 391–407. find
  17. Digital Equipment Corporation, AltaVista search engine, http://altavista.digital.com/. ↗
  18. W.E. Donath, A.J. Hoffman, “Lower bounds for the partitioning of graphs”, IBM Journal of Research and Development, 17(1973). find
  19. P. Doreian, “Measuring the relative standing of disciplinary journals,” Inf. Proc. and Management, 24(1988), pp. 45–56. find
  20. P. Doreian, “A measure of standing for citation networks within a wider environment,” Inf. Proc. and Management, 30(1994), pp. 21–31. find
  21. L. Egghe, “Mathematical relations between impact factors and average number of citations,” Inf. Proc. and Management, 24(1988), pp. 567–576. find
  22. L. Egghe, R. Rousseau, Introduction to Informetrics, Elsevier, 1990. find
  23. M. Fielder, “Algebraic connectivity of graphs,” Czech. Math. J., 23(1973), pp. 298–305. find
  24. A. Frieze, R. Kannan, S. Vempala, “Fast Monte-Carlo Algorithms for Finding Low-Rank Approximations,” Proc. 39th IEEE Symp. on Foundations of Computer Science, 1998. find
  25. M.E. Frisse, “Searching for information in a hypertext medical handbook,” Communications of the ACM, 31(7), pp. 880–886. find
  26. E. Garfield, “Citation analysis as a tool in journal evaluation,” Science, 178(1972), pp. 471–479. find
  27. N. Geller, “On the citation influence methodology of Pinski and Narin,” Inf. Proc. and Management, 14(1978), pp. 93–95. find
  28. D. Gibson, J. Kleinberg, P. Raghavan, “Inferring Web Communities from Link Topology,” Proc. 9th ACM Conference on Hypertext and Hypermedia, 1998. find
  29. D. Gibson, J. Kleinberg, P. Raghavan, “Clustering Categorical Data: An Approach Based on Dynamical Systems,” Proc. 24th Intl. Conf. on Very Large Databases, 1998. find
  30. G. Golub, C.F. Van Loan, Matrix Computations, Johns Hopkins University Press, 1989. find
  31. H. Hotelling, “Analysis of a complex statistical variable into principal components,” J. Educational Psychology, 24(1933), pp. 417–441. find
  32. C.H. Hubbell, “An input-output approach to clique identification,” Sociometry, 28(1965), pp. 377-399. find
  33. B. Huberman, P. Pirolli, J. Pitkow, R. Lukose, “Strong Regularities in World Wide Web Surfing,” Science, 280(1998). find
  34. I.T. Jolliffe. Principal Component Analysis. Springer-Verlag, 1986. find
  35. L. Katz, “A new status index derived from sociometric analysis,” Psychometrika, 18(1953), pp. 39–43. find
  36. M.M. Kessler, “Bibliographic coupling between scientific papers,” American Documentation, 14(1963), pp. 10–25. find
  37. R. Larson, “Bibliometrics of the World Wide Web: An exploratory analysis of the intellectual structure of cyberspace,” Ann. Meeting of the American Soc. Info. Sci., 1996. find
  38. J.H. Levine, “Joint-space analysis of ‘pick-any’ data: Analysis of choices from an unconstrained set of alternatives,” Psychometrika, 44(1979), pp. 85–92. find
  39. M. Marchiori, “The quest for correct information on the Web: Hyper search engines,” Proc. 6th International World Wide Web Conference, 1997. find
  40. O. McBryan, “GENVL and WWWW: Tools for taming the Web,” Proc. 1st International World Wide Web Conference, 1994. find
  41. K. McCain, “Co-cited author mapping as a valid representation of intellectual structure,” J. American Soc. Info. Sci., 37(1986), pp. 111–122. find
  42. E. Noma, “An improved method for analyzing square scientometric transaction matrices,” Scientometrics, 4(1982), pp. 297–316. find
  43. E. Noma, “Co-citation analysis and the invisible college,” J. American Soc. Info. Sci., 35(1984), pp. 29–33. find
  44. C.H. Papadimitriou, P. Raghavan, H. Tamaki, S. Vempala, “Latent semantic indexing: A probabilistic analysis,” Proc. ACM Symp. on Principles of Database Systems, 1998. find
  45. G. Pinski, F. Narin, “Citation influence for journal aggregates of scientific publications: Theory, with application to the literature of physics,” Inf. Proc. and Management, 12(1976), pp. 297–312. find
  46. P. Pirolli, J. Pitkow, R. Rao, “Silk from a sow’s ear: Extracting usable structures from the Web,” Proceedings of ACM SIGCHI Conference on Human Factors in Computing, 1996. find
  47. J. Pitkow, P. Pirolli, “Life, death, and lawfulness on the electronic frontier,” Proceedings of ACM SIGCHI Conference on Human Factors in Computing, 1997. find
  48. C.J. van Rijsbergen, Information Retrieval, Butterworths, 1979. find
  49. G. Salton. Automatic Text Processing. Addison-Wesley, Reading, MA, 1989. find
  50. W.M. Shaw, “Subject and Citation Indexing. Part I: The clustering structure of composite representations in the cystic fibrosis document collection,” J. American Soc. Info. Sci., 42(1991), pp. 669–675. find
  51. W.M. Shaw, “Subject and Citation Indexing. Part II: The optimal, cluster-based retrieval performance of composite representations,” J. American Soc. Info. Sci., 42(1991), pp. 676–684. find
  52. H. Small, “Co-citation in the scientific literature: A new measure of the relationship between two documents,” J. American Soc. Info. Sci., 24(1973), pp. 265–269. find
  53. H. Small, “The synthesis of specialty narratives from co-citation clusters,” J. American Soc. Info. Sci., 37(1986), pp. 97–110. find
  54. H. Small, B.C. Griffith, “The structure of the scientific literatures I. Identifying and graphing specialties,” Science Studies 4(1974), pp. 17–40. find
  55. E. Spertus, “ParaSite: Mining structural information on the Web,” Proc. 6th International World Wide Web Conference, 1997. find
  56. R. Weiss, B. Velez, M. Sheldon, C. Nemprempre, P. Szilagyi, D.K. Gifford, “HyPursuit: A Hierarchical Network Search Engine that Exploits Content-Link Hypertext Clustering,” Proceedings of the Seventh ACM Conference on Hypertext, 1996. find
  57. Wired Digital, Inc., Hotbot, http://www.hotbot.com. ↗
  58. Yahoo! Corporation, Yahoo!, http://www.yahoo.com. ↗