Cluster analysis for hypertext systems

ABSTRACT

Identifying nodes of information that are highly related has many applications in any information systems, and in particular in hypertext systems. In this paper we present a technique to identify “natural” clusters in a hypertext. A natural cluster is a cluster that is not arbitrary, but depends only on intrinsic properties of the hypertext. In our case, the property we will use to identify the clusters is the number of independent paths between nodes. Using the graph theoretic definition of k-edge-components we present an aggregation technique to cluster the nodes. We then use this techniques to cluster three medium sized hypertexts that were developed by different authors for different users, using different methodologies. We also show how to use clustering to improve data display, browsing and retrieval.

REFERENCES

• 1: Mark Bernstein , Jay David Bolter , Michael Joyce , Elli Mylonas, Architectures for volatile hypertext, Proceedings of the third annual ACM conference on Hypertext, p.243-260, December 15-18, 1991, San Antonio, Texas, United States [doi>10.1145/122974.122999]
• 2: R. A. Botafogo. Maximum & multi-terminal flow algorithms and their application for hypertexts. Technical Report TR-RB9201, NEC Corporation, Applied Info. Tech. Research Lab., Kawasaki, Kanagawa, Japan, 1992.
• 3: Rodrigo A. Botafogo , Ben Shneiderman, Identifying aggregates in hypertext structures, Proceedings of the third annual ACM conference on Hypertext, p.63-74, December 15-18, 1991, San Antonio, Texas, United States [doi>10.1145/122974.122981]
• 4: P. J. Brown, Do we need maps to navigate round hypertext documents?, Electronic Publishing—Origination, Dissemination, and Design, v.2 n.2, p.91-100, July 1989
• 5: Andrea Caloini, Matching hypertext models to hypertext systems, Proceedings of the ACM conference on Hypertext, p.91-101, November 30-December 04, 1992, Milan, Italy [doi>10.1145/168466.168500]
• 6: S. Even and R. E. Tarjan. Network flow and testing graph connectivity. SIAM Journal of Computers, 4(4):507-518, 1975.
• 7: Franca Garzotto , Paolo Paolini , Daniel Schwabe, HDM—a model for the design of hypertext applications, Proceedings of the third annual ACM conference on Hypertext, p.313-328, December 15-18, 1991, San Antonio, Texas, United States [doi>10.1145/122974.123004]
• 8: Frank,G. Halasz, Reflections on NoteCards: seven issues for the next generation of hypermedia systems, Communications of the ACM, v.31 n.7, p.836-852, July 1988 [doi>10.1145/48511.48514]
• 9: Y. Hara and R. A. Botafogo. Hypertext projection, clustering, and view in hypermedia databases. Submited to the Hypertext 93 conference.
• 10: Y. Hara , Y. Kasahara, A set-to-set linking strategy for hypertext systems, Proceedings of the ACM SIGOIS and IEEE CS TC-OA conference on Office information systems, p.131-135, April 25-27, 1990, Cambridge, Massachusetts, United States
• 11: Yoshinori Hara , Arthur M. Keller , Gio Wiederhold, Implementing hypertext database relationships through aggregations and exception, Proceedings of the third annual ACM conference on Hypertext, p.75-90, December 15-18, 1991, San Antonio, Texas, United States [doi>10.1145/122974.122982]
• 12: F. Harary. Graph Theory. Addison-Wesley, Reading, 1969.
• 13: John A. Hartigan, Clustering Algorithms, John Wiley & Sons, Inc., New York, NY, 1975
• 14: R. F. Ling. On the theory and construction of k-clusters. Computer Journal, 15:326-332, 1972.
• 15: D. W. Matula. k-Components, clusters, and slicings in graphs. SIAM Journal of Applied Mathematics, 22(3):459-480, 1972.
• 16: D. W. Matula. Graph theoretic techniques for cluster analysis algorithms. In J. Van Ryzin, editor, Classification and Clustering, pages 95-129. Academic Press, inc., 1977. Proceedings of an advanced seminar conducted by the Mathematics Research Center, The University of Wisconsin at Madison, May 3-5, 1976.
• 17: K. Menger. Zur allgemeiner kurventheorie. Fund. Math., 10:96-115, 1927.
• 18: Jakob Nielsen, The art of navigating through hypertext, Communications of the ACM, v.33 n.3, p.296-310, March 1990 [doi>10.1145/77481.77483]
• 19: Catherine Plaisant, Guide to opportunities in volunteer archaeology: case study on the use of a hypertext system in a museum exhibit, Hypertext/hypermedia handbook, McGraw-Hill, Inc., Hightstown, NJ, 1991
• 20: B. Shneiderman and G. Kearsley. Hypertext Hands-On! Reading, Massachusetts: Addison- Wesley Pub., 1989.
• 21: R. Sibson. An optimally efficient algorithm for the single-link cluster method. Computer Journal, 16:30-34, 1973.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Clustering

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.2 Document Preparation
          Subjects: Hypertext/hypermedia

General Terms:
Algorithms

Keywords:
aggregation, clustering, graph theory, hypertext, structural analysis