Structural analysis of hypertexts: identifying hierarchies and useful metrics

ABSTRACT

Hypertext users often suffer from the “lost in hyperspace” problem: disorientation from too many jumps while traversing a complex network. One solution to this problem is improved authoring to create more comprehensible structures. This paper proposes several authoring tools, based on hypertext structure analysis. In many hypertext systems authors are encouraged to create hierarchical structures, but when writing, the hierarchy is lost because of the inclusion of cross-reference links. The first part of this paper looks at ways of recovering lost hierarchies and finding new ones, offering authors different views of the same hypertext. The second part helps authors by identifying properties of the hypertext document. Multiple metrics are developed including compactness and stratum. Compactness indicates the intrinsic connectedness of the hypertext, and stratum reveals to what degree the hypertext is organized so that some nodes must be read before others. Several existing hypertexts are used to illustrate the benefits of each technique. The collection of techniques provides a multifaceted view of the hypertext, which should allow authors to reduce undesired structural complexity and create documents that readers can traverse more easily.

REFERENCES

• 1: BOTAFOGO, R.A. Structural ana}ysis of hypertexts. Unpublished Master's Thesis, Umv. of Maryland, College Park, 1990.
• 2: 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]
• 3: 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
• 4: Davida Charney, Comprehending non-linear text: the role of discourse cues and reading strategies, Proceeding of the ACM conference on Hypertext, p.109-120, November 1987, Chapel Hill, North Carolina, United States [doi>10.1145/317426.317436]
• 5: Jeff Conklin , Michael L. Begeman, gIBIS: a hypertext tool for exploratory policy discussion, ACM Transactions on Information Systems (TOIS), v.6 n.4, p.303-331, Oct. 1988 [doi>10.1145/58566.59297]
• 6: Dennis E. Egan , Joel R. Remde , Louis M. Gomez , Thomas K. Landauer , Jennifer Eberhardt , Carol C. Lochbaum, Formative design evaluation of superbook, ACM Transactions on Information Systems (TOIS), v.7 n.1, p.30-57, Jan. 1989 [doi>10.1145/64789.64790]
• 7: Robert W. Floyd, Algorithm 97: Shortest path, Communications of the ACM, v.5 n.6, p.345, June 1962 [doi>10.1145/367766.368168]
• 8: G. W. Furnas, Generalized fisheye views, Proceedings of the SIGCHI conference on Human factors in computing systems, p.16-23, April 13-17, 1986, Boston, Massachusetts, United States
• 9: Frank G. Halasz , Thomas P. Moran , Randall H. Trigg, Notecards in a nutshell, Proceedings of the SIGCHI/GI conference on Human factors in computing systems and graphics interface, p.45-52, April 05-09, 1987, Toronto, Ontario, Canada
• 10: 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]
• 11: HARARY, F. Status and contrastatus Sociometry 22 (1959), 23-43.
• 12: HARARY, F., NORMAN, R. Z., AND CARTWRIGHT, D. Structural models. An Introduction to the Theory of D~rected Graphs. Wiley, New York, 1965
• 13: KAUFMANN, A. Graphs, dynamic programming and finite gaines. In Mathematzcs *n Sczence and Engineering 36. Academic Press, New York 1967.
• 14: KINTSCH, W , AND VAN DIJK, T. Toward a model of text comprehensmn and production Psychol. Rev. 85 (1978), 363-394.
• 15: C. C. Marshall , P. M. Irish, Guided tours and on-line presentations: how authors make existing hypertext intelligible for readers, Proceedings of the second annual ACM conference on Hypertext, p.15-26, November 1989, Pittsburgh, Pennsylvania, United States [doi>10.1145/74224.74226]
• 16: MOFFAT, A. AND TAKAOKA, T An all pairs shortest path algomthm with expected running time O(n2 log n). In Proceedmgs of the 26th Annual Sympostum on Foundations of Computer Smence, 1985, pp. 101 105.
• 17: 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]
• 18: Jakob Nielsen, Hypertext and hypermedia, Academic Press Professional, Inc., San Diego, CA, 1990
• 19: Christine Neuwirth , David Kaufer , Rick Chimera , Terilyn Gillespie, The Notes program: a hypertext application for writing from source texts, Proceeding of the ACM conference on Hypertext, p.121-141, November 1987, Chapel Hill, North Carolina, United States [doi>10.1145/317426.317437]
• 20: R. Pausch , J. Detmer, Node popularity as a hypertext browsing aid, Electronic Publishing—Origination, Dissemination, and Design, v.3 n.4, p.227-234, Nov. 1990
• 21: 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
• 22: Gerald Salton, Automatic text processing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
• 23: SHNEIDERMAN, B , AND KEARSLEY, G. Hypertext Hands-On/Addison-Wesley, Reading, Mass, 1989
• 24: SIRA, P.M. A new algorithm for finding all shortest paths in a graph of posture arcs in average time O(n2 tog2 n), SIAM J. Comput. 2, I (1973), 28-32.
• 25: P. David Stotts , Richard Furuta, Petri-net-based hypertext: document structure with browsing semantics, ACM Transactions on Information Systems (TOIS), v.7 n.1, p.3-29, Jan. 1989 [doi>10.1145/64789.64791]
• 26: P. David Stotts , Richard Furuta, Hierarchy, composition, scripting languages, and translators for structured hypertext, Hypertext: concepts, systems and applications, Cambridge University Press, New York, NY, 1992
• 27: Randall H. Trigg , Peggy M. Irish, Hypertext habitats: experiences of writers in NoteCards, Proceeding of the ACM conference on Hypertext, p.89-108, November 1987, Chapel Hill, North Carolina, United States [doi>10.1145/317426.317435]
• 28: VALnEZ, F , AN~ CHI~NELL, M Browsing models for bypermedia databases. In Proceedings of the Human Factors Soczety, 32nd Annual Meeting (Santa Monica, Calif., 1988), Human Factors Society, 1988, pp. 318 322.
• 29: VAN DIJK, T, AND KINTSCm W Strategzes of Discourse Comprehensmn. Academic Press, New York, 1983.
• 30: P. T. Zellweger, Scripted documents: a hypermedia path mechanism, Proceedings of the second annual ACM conference on Hypertext, p.1-14, November 1989, Pittsburgh, Pennsylvania, United States [doi>10.1145/74224.74225]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.1 Multimedia Information Systems
          Subjects: Hypertext navigation and maps**

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.2 Information Storage
          Subjects: File organization
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)

General Terms:
Design, Documentation, Human Factors, Measurement

Keywords:
graph theory, hierarchies, hypertext, metrics, structural analysis