3.1 Web Site Topology

The web site is depicted as a directed graph, with pages as nodes, and links as edges. VISVIP automatically generates a 2D layout of the graph, using a force-directed algorithm. In our model, adjacent nodes exert a spring-like force on each other - they "try" to set themselves apart at a fixed distance. Non-adjacent nodes repel each other with a force inversely proportional to the distance between them. Initially we tried using the more familiar "inverse of distance squared" rule, but found that the graph did not spread out well enough because the repulsive force effectively vanished over longer distances. Finally there is a third force that weakly attracts all nodes towards the origin; this serves to keep parts of the graph that become unconnected from flying off to infinity.

The UE can dynamically adjust the constants of the underlying force model so as to control the overall density and appearance of the graph. Also, for finer control, the UE can drag and drop individual nodes into precise locations as desired.

In our early implementations, we generated a 3D layout for the web site graph. While easy to produce, it was difficult to interpret, especially when the subject paths were overlaid. Therefore, we kept the web site layout as a 2D structure, and "saved" the 3rd dimension for timing information (see below).

3.2 Web Site Content

Because URLs tend to be long, a brief nickname is generated for each page, normally the ten characters immediately preceding the filetype. For example, an URL such as "http://www.wherever.com/animals/giraffe.gif" would be nicknamed "ls/giraffe". Each node is shown as a small named box. The box is color-coded to reflect the page type (e.g. HTML, image, video, audio, mailto, directory, etc.). Sliding the mouse over a node causes it to be highlighted to indicate that it is currently selected, and the full URL and filetype of the page appear at the top of the window. The selected page can be displayed in Netscape.

3.3 Web Site Simplification

A web site may possess a simple structure that generates a comprehensible display. The site in Figure 1, for example, approximates a balanced tree (see [5] for full-size color figures). Others do not lend themselves so easily to good visualization. We found several common problems: first, some web sites have a lot of "noise" nodes, such as images and mailto nodes. These nodes usually are not significant in tracing subjects' paths. Therefore VISVIP allows the user to request suppression of all nodes of a specified type, or of individual nodes. If such a node is traversed by a path, however, it will nonetheless be displayed as part of the graph.

Figure 1. A typical web site layout

A second problem was "over-connectivity". In some web sites, all the pages have a link back to a home page. Also, there may be an image (such as a company logo) that appears on every page. The result is a graph with so many edges that the visualization is confusing (see Figure 2). While it may be reasonable to delete the node with a company logo, suppressing the home page is probably not a good solution. VISVIP offers two mechanisms to simplify the display by deleting edges: first, one can select a node and direct that all edges leading to that node be deleted. Second, and more drastic, you can select a node, such as the home page, and direct that the graph be simplified to a tree, using that node as the root.

Figure 2. A Highly Connected Web site

Finally, if the web site is large, and a subject's path is confined to a small section of it, it may be helpful to concentrate on only that part of the web site. Therefore VISVIP supports the suppression of nodes more than a given distance from any displayed path, e.g. all nodes more than two links away can be suppressed.

3.4 Path Sequence

Given this visual layout of the web site, our next step is to depict the subjects' paths through it. In early versions of VISVIP, we showed the paths simply as straight line segments connecting the successive nodes. Two problems became evident: first, it was hard to visually follow a single jagged path, and second, when several paths were shown at once or when a single path backtracked, it was difficult to distinguish among them.

We then adopted a spline representation: each subject path is depicted as a smooth curve overlaid on the directed graph. Each subject is coded with a distinct name and color. VISVIP also allows the UE to specify the colors manually so as to examine groups of subjects (e.g. novices vs. experts). The spline curves are decorated with arrowheads to indicate direction, and a special curvy arrow into and out of the plane of the graph highlights the starting and ending point of the path.

The UE may dynamically select any subset of paths to be viewed at any time. The appearance or suppression of nodes is automatically updated insofar as it is dependent on the paths. Often, we found it useful to start by viewing all the paths to get a general sense of which parts of the web site the subjects were visiting. One could then easily identify paths that deviated from the norm and examine these outliers individually.

Figure 3. Path laid over a web site

3.5 Path Timing

Of course, an important aspect of the path data is the time the subject spent at each node. This is represented by a dotted vertical bar with its base on the node of the page where the time was spent, and its height (in the 3rd dimension, orthogonal to the plane of the graph) proportional to the amount of time. In order to avoid overlap, VISVIP offsets the base location slightly in one dimension, depending on the subject, and in the second dimension, depending on total time spent so far (the latter to prevent overlap from a subject's revisiting the same page). Pages where subjects spent a long time or which were heavily visited are immediately evident (Figure 3).

In addition to the static display, VISVIP provides animation facilities for the visualization of path traversal. As the animation progresses, a horizontal "current time" indicator proceeds from the base of the vertical time bar to the top. When it hits the top (representing a jump from this page to the next), the next segment of the spline curve becomes visible, and the indicator starts moving up from the base of the next page. The UE can dynamically adjust the playback speed (10-30 times real-time is typical), and pause or re-start.

The UE can also directly control the animation with a slider to set the virtual time represented by the display. By moving the slider back and forth, the UE can effectively play the animation backward or forward, or pause at a time of special interest. The slider displays the number of seconds elapsed since the beginning of the paths.

Finally, the UE may select a node and generate a detailed timing table, displayed in Netscape, for the corresponding page. The table shows all visits by all subjects to that page, how long each visit took, and the total path time elapsed just prior to each visit (see Figure 4).

Figure 4. Detailed timing data

3.6 Path Topology

As Figure 3 illustrates, one cannot suppose that the structure of subjects' paths will neatly align with the intrinsic static structure of the web site being traversed. Basing the organization of the graph on the inherent web site topology is good for seeing what parts of the web site are being heavily visited or avoided.

However, we found that the inherent topologies of the paths are also informative for discovering similarities and differences among subjects' navigation styles. Our force-directed graph layout algorithm depends only on whether pairs of nodes are adjacent (directly connected) or not. Therefore VISVIP lets the UE dynamically choose whether adjacency for a pair of nodes means "connected by a static link" as described so far, or "a displayed subject path jumps directly from one to the other". Paths that looked complicated when laid out directly over a web site often revealed a much simpler structure when laid out according to their own topology (see Figure 5). Indeed, our preliminary inspection seemed to show certain distinct patterns of activity by various subjects: some do very little backtracking; others seem to circle around; others keep returning to an anchor page, perhaps for orientation.

Figure 5. Natural topology of a path