Hypermedia Topologies and User Navigation
H. Van Dyke Parunak
Industrial Technology Institute
PO Box 1485
Ann Arbor, MI 48106
(313) 769-40 van@iti.org
ABSTRACT
One of the major problems confronting users of large hypermedia systems is that of navigation: knowing where one is, where one wants to go, and how to get there from here. This paper contributes to this problem in three steps. First, it articulates a number of navigational strategies that people use in physical (geographical) navigation. Second, it correlates these with various graph topologies, showing how and why appropriately restricting the connectivity of a hyperbsse can improve the ability of users to navigate. Third, it analyzes some common hypermedia navigational mechanisms in terms of navigational strategies and graph topology.
1. PROBLEM DEFINITION
Hypermedia is a set of nodes of information (the “hyperbase”) and a mechanism for moving among them. One important criterion for classifying hypermedia is the topology of the links that join different nodes together. The degenerate case is the traditional book, in which the nodes of information are paragraphs, and the topology is simply a linear chain. Much of the power of computer-based hypermedia comes from its ability to manipulate more complex topologies, such as hierarchies, hypercubes, lattices, or even complete graphs.
As the complexity of the topology underlying a hypermedia system increases, users have more ways to move from one information node to another, and thus can potentially find shorter paths to desired information. This very richness quickly leads to the problem of users becoming “lost in hyperspace,” reported as early as the ZOG work [RobeSl].
2. COMMON NAVIGATIONAL STRATEGIES
Long before the advent of hypermedia, humans developed a number of navigational strategies to find their way around the world. This section articulates five of them, illustrating them from the domain of geographical navigation.
2.1. Identifier
The Identifier Strategy associates a unique identifier or description with each entity of interest, thus permitting the searcher to recognize the target. By itself, this strategy degenerates to exhaustive search (although, with the appropriate hardware, this search can be reasonably fast: consider using a helicopter to find a house with a fluorescent orange star painted on the roof). In the form of exhaustive search, it is applicable to any countable set of entities. More commonly, it is a component of other strategies.
2.2. Path
The Path Strategy gives the searcher a procedural description of how to get to the target: “Turn left at the first light and right at the second gas station, and it’s the blue house [Identifier Strategy] on the right.” The Path Strategy is useful in any countable space in which the number of links originating with any one node is typically much less than .the total number of nodes. (If this is not the case, the task of finding the next step in a path is not significantIy easier than going directly from the start to the target.)
Some topologies define a unique path between any two nodes. (We consider two paths the same if they contain the same links, even if one path traverses some of those links more often than does the other.) Other topologies permit multiple paths. One may conjecture that a small number of aiternate routes is easier to use than either a single route or a large number of routes, but this is a matter for experimental investigation and is not pursued here.
2.3. Direction
Travelers apply the Direction Strategy when they follow directions such as “Go due north.” Like the path strategy and unlike the identifier strategy, the direction strategy avoids exhaustive search. It differs from the path strategy in the framework that the traveler uses for guidance. In the path strategy, this framework is local to an individual node, and is stated in terms of the links originating at that node. In the direction strategy, the framework is global to the entire system, part of the niatrix in which the nodes are embedded.
Directional frameworks can vary in their granularity. The coarsest defines one dimension (say, “north” vs. “south”), and cuts the search plane into two pieces. Finer systems include not only the four cardinal points (North, South, East, West), but intermediates (NE, NNE, ENE), and ultimately the full “degrees, minutes, seconds” of modern navigation.
The direction strategy as humans use it in geography depends on two characteristics of the embedding space: texture and comparability. Texture is the existence of some field or distinguished point relative to which directions can be established. Comparability is the existence of a relation (in this case, the direction relation) between any two points of the space. A sphere would naturally have no texture, but people on earth have used various features of our sphere to define direction: its axis of rotation (reflected in the direction of sunrise and the apparent stability of the pole star); its magnetic field; or the direction of flow of a prominent river (for example, the Nile in ancient Egypt). Comparability exists for geographic directions with the fine granularity of modern systems, but a primitive system that distinguishes only north from south cannot define a direction between two locations at the same latitude, and so lacks comparability. Thus we can distinguish three classes of systems from the perspective of directionality: those with no directionality, those with texture but not comparability, and those with both texture and comparability.
2.4. Distance
The Distance Strategy bounds search to a circle around the traveler’s current location, which can be expressed in terms either of space or of time: “It’s only a mile [ten minutes] from here.” It is often used in connection with the direction strategy: “Go south for two kilometers.” Like the path strategy, the distance strategy varies between topologies where a unique distance separates two points and those in which different paths provide different distances. Any space that supports the path strategy also supports the distance strategy, since distance can be defined along the path. Unique paths imply unique distance, but we will see an example of a space in which multiple paths exist but distances are still unique. Also like the path strategy, the distance strategy becomes degenerate in spaces in which one can move directly from any one point to any other.
2.5. Address
The Address Strategy refines the direction strategy by establishing an orthogonal set of coordinates: “Go to the corner of Huron and Division.” For n dimensions with m divisions each, this approach reduces the search space from O(mn) to O(m), since one can search each dimension independently.
3. MATCHING STRATEGIES WITH TOPOLOGIES
Our survey of navigational strategies has already suggested some restrictions on the kinds of spaces to which each can be applied. In this section, we develop a taxonomy of topologies for hypermedia, and identify the navigational strategies that can be used with each.
3.1. Definitions
The underlying model in which we couch our discussion of hypermedia topologies is graph theory.
The underlying model in which we couch our discussion of hypermedia topologies is graph theory.
For our limited purposes, a hyperbase H is an ordered pair H= <N,L> where N is a finite set of information nodes and L is a set of directed links between pairs of nodes, defined in turn as ordered pairs <m,n> of elements of N. Intuitively, a user can move directly from one node m to another n just when there is a link <m,n> 3.1. Definitions
The underlying model in which we couch our discussion of hypermedia topologies is graph theory.
The underlying model in which we couch our discussion of hypermedia topologies is graph theory.
For our limited purposes, a hyperbase H is an ordered pair H= <N,L> where N is a finite set of information nodes and L is a set of directed links between pairs of nodes, defined in turn as ordered pairs <m,n> of elements of N. Intuitively, a user can move directly from one node m to another n just when there is a link <m,n> 3.1. Definitions
The underlying model in which we couch our discussion of hypermedia topologies is graph theory.
The underlying model in which we couch our discussion of hypermedia topologies is graph theory.
For our limited purposes, a hyperbase H is an ordered pair H= <N,L> where N is a finite set of information nodes and L is a set of directed links between pairs of nodes, defined in turn as ordered pairs <m,n> of elements of N. Intuitively, a user can move directly from one node m to another n just when there is a link <m,n> ∈ L between them, and the directionality of a link reflects the “normal” direction of traversal, which we assume is accessed differently by the user than the reverse direction. For example, one may be able to traverse a link in reverse only if one has first traversed it in the forward direction. Every hyperbase is thus trivially isomorphic to a finite directed graph G = <V,U>, by identifying the nodes N of H with the points V of G, and the links L of H with the arcs Uof G.
For two nodes n,m, we write P(n,m) (read “n is a parent of m”) iff <n,m> ∈ L, and A(n1,nm) (“n1 is an ancestor of nm”) iff ∃n1,n2,…,nm-1,nm∈N:P(nl,n2)&…&P(nm-1,nm). To these relations there correspond unary set-valued functions P(m) (the set of all the parents of m) and A(m) (the set of all the ancestors of m). We similarly define relations and functions C,D for children and descendants. For any set S, Card(S) is the cardinality of S.
We assume that any hyperbase under discussion is accessible, which means ∃m ∈ N:∀n ∈ N-m:A(m,n).
Our definition of N as a set implies that all of its elements are distinguishable, and thus at a minimum the identifier strategy described above is applicable to any hyperbase.
3.2. Linear
The simplest topology is linear, in which each node has at most one child and one parent: ∀n ∈ N:(Card(P(n)) ≤ l)∧(Card(C(n)) ≤ 1) (Figure 1). If the inequalities are replaced with equalities, one has the special case of a ring. Otherwise, because of our accessibility assumption, exactly one node has no child and exactly one node has no parent, and the structure is a chain with these two nodes as its ends.
The non-ring linear topology supports all of the navigational strategies discussed in the last section, though they are hardly necessary, given the simplicity of the structure. The path strategy differs little from the ubiquitous identifier strategy, since in both cases one simply traverses the linear list of links. Accessibility and the limitation of one child and one parent per node imply that all links are head-to-tail, never head-to-head or tail- to-tail. Thus the structure defines a natural texture for directionality, and exhibits comparability as well. There is a unique distance between any two nodes, defined as the number of links between them, and a unique (though trivial) address for each.
In a ring topology, as in a sphere, there is no natural texture and thus no directionality, though one may be imposed by a distinguished entry point. Paths and thus distances are unique, as in the non-ring case.
3.3. Hierarchy
In a hierarchical topology, one node has no parents and the others have exactly one parent: (∃m ∈ N:Card(P(m)) = 0)&(∀n ∈ N—m:Card(P(n)) == 1) (Figure 2). This topology characterizes popular PC-based outline processors such as ThinkTank™ or PCOutline™.
The orphan element (the root of the hierarchy) is the node at which one enters the hyperbase. All links point away from the root, so any node is reachable from it. Furthermore, since a link once traversed can be followed in the reverse direction, one can go from any node back up (to the root if necessary), and then down to any other node. A unique path exists between any two nodes: from the current node, back up repeatedly to the unique parent of the current node until one reaches a node that is an ancestor of the target node, then along forward links to the target node. The existence of unique paths also implies unique distances between nodes, which are conveniently abstracted in terms of depths in the hierarchy of any two nodes and their nearest common ancestor. If the root is level 0, and two nodes at levels i and j have a nearest ancestor (least upper bound) at level k, then the distance between them is (i-l)+(j-k). Hierarchies exhibit texture (toward or away from the root), but not comparability. The address strategy is not supported, though the unique path from the root to any node serves as a useful identifier of that node.
3.4. Hypercube/Hypertorus
The hypercube/hypertorus topology directly supports the address strategy for navigation, and is useful for domains that invite one to compare a number of items along a number of dimensions. An experimental implementation of this topology, SymEdit, is a useful tool for studying symmetrical patterns in literary documents, where one wishes to trace common themes through a number of different passages. More generally, many problems take the form of comparing a set of cases along a set of characteristics, and the hypercube organization is ideally suited to this task. Informally, the two-dimensional version of a hypercube-based hypertext may be thought of as a spreadsheet for text, in which each node is directly adjacent to four others, one on each side (Figure 3).
More formally, define the union of two hyperbases H1∪H2 in the natural way as the hyperbase whose nodes are the union of the nodes of each of the original hyperbases and whose links are the union of the links of the originals. We do not require that the original sets of nodes be disjoint, or that the original sets of links be disjoint. A hyperbase with a m-dimensional hypercube topology is any that can be constructed as follows:
1.Initially, H== <N,∅>. Determine m integer factors F1,…,Fm such that ∏mi==1 Fi. == Card(N). (Add dummy nodes factorization.)
2. For i == 1 to m
a. Partition N into Fi sets Ni1,…,NiFi each with Card(N)/Fi elements.
b. For j == 1 to Fi
i. Define a set Lij of Card(Nij)-1 links among the members of Nij
such that Hij==<Nij,Lij> has a linear topology.
such that Hij==<Nij,Lij> has a linear topology.
ii. H ← H∪Hij
As a result of this construction, each element has a unique address <a1 ∈ [1..F1],a2 ∈ [1..F2],…, am ∈ [l..Fm]>, and the search to reach any node is on the order of ∑m i==1Fi instead of ∏m i--1Fi, since each dimension may be searched separately.
Two interesting refinements of this topology are possible.
First, if the Hij are constrained to be rings instead of linear, we construct a hypertorus instead of a hypercube.
Second, our informal picture of a two-dimensional hypercube as a spreadsheet implies that the network is isomorphic to a rectangular lattice (without crossing links). The formal construction does not enforce this constraint, which is not necessarv for the address strategy for navigation, and so defines a tangled hypercube or hypertorus. The constraint of isomorphism to a rectangular lattice of the appropriate dimensionality can be added for domains in which natural orderings can be imposed on each dimension, yielding an ordered hypercube or hypertorus.
In general, a hypercube or hypertorus topology supports (nonunique) paths and distances. If the structure is ordered instead of tangled, paths are still nonunique, but distances (defined with a city block metric) are unique, and if the ordering further constrains ail links in any hyperplane of the hypercube to be parallel (rather than opposing a hypercube exhibits both texture and comparability. Without a distinguished point, a hypertorus (like a sphere) does not support either, even if it is ordered.
3.5. DAG
The constraint ∀m ∈ N:A(m)∩D(m) = 0 yields a DAG (Directed Acyclic Graph) topology (Figure 4).
Most implementations have a single point of entry, forming a common ancestor of all nodes and yielding a semilattice. A DAG does not support the address strategy, but it does support nonunique paths and thus nonunique distances, and the absence of cycles together with accessibility defines texture (though not comparability).
3.6. Arbitrary
The least constrainted topology consists of any connected graph. If none of the constraints described above applies, the identifier, path, and distance strategies are the only ones available. Even the path strategy becomes useless as the graph approaches a complete graph, for then the navigational problem involved in selecting the next step along a path approaches the problem of going directly to the target node. So we may distinguish a partial arbitrary topology from a complete arbitrary topology, based on the degree of the nodes.
3.7. Summary
Figure 5 summarizes our conclusions about which topologies support which navigational strategies.
4. NAVIGATIONAL AIDS IN HYPERMEDIA
Many navigational aids commonly implemented in hypermedia systems are effectively mechanisms for inducing a topology of reduced complexity on the hyperbase, and thus enlarging the set of navigational strategies that users can bring to bear. The aids that fit this characterization can be grouped into two classes: “beaten path” aids that help users find places they have already been, and typed links. Other aids, such as maps, do not induce a restricted topology, but are only useful under certain conditions that can be topologically characterized.
4.1. “Beaten Path” Mechanisms
“Beaten Path” navigational aids enable a user to return easily to places already visited, and include back-up stacks, path macros, and book marks.
A back-up stack keeps track of the nodes through which a user has moved, so that the steps can be retraced, bringing one back to the starting point. It induces a subspace with linear topology on the hyperbase, thus permitting application of the widest range of navigational strategies.
A generalization of the back-up stack is the path macro, which remembers a path and permits the user to move back and forth along it repeatedly, in essence building a subspace of more limited topology within which navigation is simpler. It records the most recent path of specified complexity (usually linear or hierarchical). In the case of a hierarchical path macro, when the user visits a node already in the macro along a different path, the older link to the node is removed from the macro and replaced with the newer one.
Book marks permit users to identify particular landmark nodes and jump directly to them from any point of the system. A book mark facility induces a one-level hierarchy whose root is the known entry point (for example, a pop-up window that lists marked locations). A home button that takes the user immediately to the entry point of the hyperbase is a degenerate example of a book mark.
4.2. Typed Links
If links are classified by different types, the topology induced by links of any one type may be much simpler than the overall topology of the entire system. For example, consider a one-level dictionary (a hierarchical topology) attached to a hierarchical hyperbase. The overall topology is a DAG, since one can access a single node of the dictionary from many different nodes of the main hyperbase. However, since each system is a hierarchy, and since the user distinguishes between accessing definitions and roaming about the main hyperbase, the distance strategy that ordinarily is not available in a DAG is still defined.
[Ande65] argues persuasively that while hierarchies are appealing because of their cognitive tractability, they do not capture the complexity of the real world. A parade example is the classification of four objects: a watermelon, an orange, a baseball, and a football. Different classificational structures emerge depending on whether we start with shape or origin (natural vs. artificial). In this case and many others, the world does not lend itself to hierarchical structuring, but people tend to think about it in terms of hierarchies anyway, even if they must be multiple hierarchies that are structurally inconsistent with one another.
The insight for hypermedia is that a hyperbase structured as a set of distinguishable hierarchies will offer navigational and other cognitive benefits that an equally complex system of undifferentiated links does not, even if the union of all the hierarchies is not itself hierarchical. The different classes of aggregation defined by ]Garg88] are in effect classes of predefined hierarchies in a hyperbase.
The notion of combining simpler well-defined topologies to control the complexity of the larger system is anticipated in the context of menu systems in [Brow82].
4.3. MapsA common feature of many hypermedia implementations is the use of maps, or graphical displays of nodes (often showing their titles, but with their contents hidden) and the links among them’. An architype is the NoteCards Browser [Hala88]. [Conk87], among others, notes the difficulty of using maps productively for large systems, but the problem is not just one of size. Useful maps can be defined for extremely large systems of appropriately constrained topology. For example, NoteCards and Neptune support maps of subnetworks restricted by link attributes. The analogy of geographical systems suggests that either non-trivial paths and distances (as on an automobile touring map) or a fine-grained directional system (as on a marine navigational chart) permits a reasonable map, at least for portions of the system. The tangled web exhibited by Conklin has some nodes of very high degree, leading to locally degenerate paths and distances. It would be interesting to determine experimentally how navigational success varies as a function of the ratio Card(N)/Card(L) for hyperbases of arbitrary topology.
5. CONCLUSION
The problem of navigation in hyperspace can be addressed by considering the navigational strategies that people apply in the physical world. The availability of these strategies in a hyperbase depends on the topology of the hyperbase. We have articulated a number of strategies, defined several topologies, identified the match between these two sets, and suggested how some common navigational aids can be understood in terms of a topological model.
REFERENCES
[Ande65] Anderson, C., “A City is Not A Tree.” Architectural Forum 122, 58ff.
[Brow87] Brown, J.W., “Controlling the Complexity of Menu Networks.” CACM 25:7 (July), 412–418.
[Conk87] Conklin, J., “Hypertext: An Introduction and Survey.” IEEE Computer 20:9 (September), 17–41.
[Garg88] Garg, P.K., “Abstraction Mechanisms in Hypertext.” CACM 31:7 (July), 862–870.
[Hala88] Halasz, F.G., “Reflections on NoteCards: Seven Issues for the Next Generation of Hypermedia Systems.” CACM 31:7 (July), 836–852.
[Robe81] Robertson, G., D.McCracken, and A.Newell, “The ZOG Approach to man-machine communications.” International Journal of Man-machine Studies 14, 461–488.
[Source: H. Van Dyke Parunak. 1989. Hypermedia topologies and user navigation. In Proceedings of the second annual ACM conference on Hypertext (HYPERTEXT '89). Association for Computing Machinery, New York, NY, USA, 43–50. https://doi.org/10.1145/74224.74228 ]
Powered by Mintter + The Hypermedia Protocol