http:^^www.cc.gatech.edu^gvu^people^phd^sougata^chi95^sm_bdy.html

This data set contains WWW-pages collected from computer science departments of various universities

translation of the graph to a tree and during the visualization of the tree.
<UL>
<LI> Translation phase:
<UL>
<LI> The users can control the various variables that are used in the translation 
process. For example, they can control the variable which specifies the maximum possible
depth of the tree (the recursion stops when this depth is reached).
<LI> The user can control the relative importance of the various submetrics in the 
overall metric that is used to rank a given pre-tree. For example the user can specify 
that the "goodness" of a root is not a useful criteria for judging pre-trees. The user
can also assign different weights to different link types to influence the submetric 
calculating the amount of information lost.
<LI> The algorithm generally selects the best possible pre-tree at each level.  However, 
the user can choose the pre-tree instead. The user is shown the possible pre-trees that 
can be selected ranked by the metric and the user can choose one of them. The user can 
specify to what level of the hierarchy the pre-trees would be chosen. By choosing 
different pre-trees during different runnings of the algorithm, different hierarchies, 
giving different perspectives to the data can be formed. 
</UL>
<LI> Visualization phase:
<UL>
<LI> Besides a 2D tree, the hierarchy can also be visualized as Cone Trees, Treemaps
or as a Table of Contents of a book (which is formed by listing the nodes in the order of
a depth-first search).
<LI> Different visual attributes can be bound to information attributes in the views. 
This is an extension of the work reported in <!WA13><A HREF="http://www.cc.gatech.edu/gvu/people/Phd/sougata/chi95/sm_bdy.html#Muk94a">[10]</A>.
</UL>
</UL>

<H2>IMPLEMENTATION</H2>
The algorithm has been implemented in the Navigational View Builder, a system for forming 
overview diagrams of hypermedia systems. Figure 2 represents an overview diagram of an 
automobile database. There are a lot of interconnected nodes showing, for example, textual
information about the cars, images of the cars, TV advertisements and audio of previous 
buyers' comments. There are also links to other cars with similar price and other models 
by the same manufacturer. From this complex network a hierarchy can be formed 
automatically. The top-level root of this tree and its children are shown in the left hand
screen of Figure 3. In this case, the attribute <em>Price</em> was used to form the 
initial partitioning and the root represents a cluster for all the nodes.
<P>
<!WA14><A HREF="http://www.cc.gatech.edu/gvu/people/Phd/sougata/chi95/sm_fg2.gif#init_auto"> FIGURE 2: </A>
An overview diagram of an automobile database. The diagram is very difficult
to comprehend.
<P>
<!WA15><A HREF="http://www.cc.gatech.edu/gvu/people/Phd/sougata/chi95/sm_fg3.gif#tree1"> FIGURE 3: </A>
The left hand screen shows the default tree formed for the automobile database. The 
top-level partitioning is by the attribute <em>Price</em>. The right hand screen shows 
the tree formed if the top-level partitioning is done by the attribute <em>Country</em>.
<P>
The user can form different hierarchies by selecting other pre-trees. For example, if the 
user wanted to select the pre-tree at the initial level, the dialog box shown in 
Figure 4 pops up. If the user wants to partition based on the attribute <em>Country</em>, 
the tree shown in the right hand screen in Figure 3 is formed. In this figure some of the 
children represents clusters for countries. For example the node labeled Japan represents 
all the Japanese cars and its children are shown in the left hand screen of Figure 5. Here
the partitioning is done by the attribute <em>Manufacturer</em>. For some other countries 
the nodes in the cluster formed a tree. In these cases the roots of the tree were 
identified by structural analysis and they became the children of the overall root. Thus 
for Sweden, Saab-Info is the root of the tree for all nodes related to Swedish cars.  Its 
children are shown in the right hand screen of Figure 5. 
<P>
<!WA16><A HREF="http://www.cc.gatech.edu/gvu/people/Phd/sougata/chi95/sm_fg4.gif#choice"> FIGURE 4: </A>
At each level various pre-trees can be used. A metric ranks these pre-trees. By default 
the pre-tree with the best metric is selected. However, the user can select others using 
the above menu.
<P>
<!WA17><A HREF="http://www.cc.gatech.edu/gvu/people/Phd/sougata/chi95/sm_fg5.gif#tree2"> FIGURE 5: </A>
Examples of Content and Structural analysis for forming pre-trees. The left hand
screen represents the nodes for Japan. The root is a cluster representing all Japanese 
cars. The nodes are partitioned by the attribute <em>Manufacturer</em>. The right hand 
screen is for Swedish cars. These nodes form a tree with the node Saab-Info as the root.
<P>
Figure 6 shows a 3D Tree view of this hierarchy. In this view, the colors of the nodes 
represent various countries and the colors of the links represent link types. Various 
zooming and filtering operations that are mentioned in 
<!WA18><A HREF="http://www.cc.gatech.edu/gvu/people/Phd/sougata/chi95/sm_bdy.html#Rob91">[15]</A> are possible for this 3D tree. Moreover, smooth 
animation is used so that the view changes are not abrupt and allow the user to see the 
changes easily. (Note that the implementation is done using C++, Motif and Open Inventor 
<!WA19><A HREF="http://www.cc.gatech.edu/gvu/people/Phd/sougata/chi95/sm_bdy.html#Wer94">[18]</A>.)
<P>
<!WA20><A HREF="http://www.cc.gatech.edu/gvu/people/Phd/sougata/chi95/sm_fg6.gif#cone"> FIGURE 6: </A>
A 3d tree View of a hierarchy of the automobile database. Initial partitioning by the
attribute <em> Country.</em> Node colors represent different countries and the link colors
different link types.

<H2>Forming Hierarchies in the World-Wide Web</A></H2>
Let us now look at an example from perhaps the most popular hypermedia system, the
<em>World-Wide Web</em>. For input to the Navigational View Builder, information was 
automatically extracted from the WWW about the various files, their authors, their links 
to other files and other information by parsing the HTML documents using the method 
described in <!WA21><A HREF="http://www.cc.gatech.edu/gvu/people/Phd/sougata/chi95/sm_bdy.html#Pit94">[14]</A>. Figure 7 shows an unstructured overview 
diagram of the WWW pages about the research activities at the Graphics Visualization 
&amp; Usability (GVU) Center at Georgia Tech. 
(URL: http/::/www.gatech.edu/gvu/gvutop.html) Obviously, this information is very complicated. 
<P>
<!WA22><A HREF="http://www.cc.gatech.edu/gvu/people/Phd/sougata/chi95/sm_fg7.gif#init-od"> FIGURE 7: </A>
An overview diagram of the World-Wide Web pages about the research activities at GVU. It 
indicates clearly why traditional overview diagrams are useless for real-world hypermedia systems.
<P>
The left hand screen of Figure 8 shows the top level of the hierarchy automatically 
created for the data by the system. The file <em>research.html</em> which lists the 
various research activities of the GVU Center is the root. It has branches to the major 
research area as well as to <em>gvutop.html</em>, a file containing general information 
about GVU. The right hand side of Figure 8 shows a view of a section of this hierarchy 
where the nodes are listed as a table of content of a book.
<P>
<!WA23><A HREF="http://www.cc.gatech.edu/gvu/people/Phd/sougata/chi95/sm_fg8.gif#book"> FIGURE 8: </A>
The left hand screen shows the top level of the default hierarchy formed for the
GVU WWW pages.  <em>research.html</em> is the root and the major research areas are shown.
The right hand screen shows a book view of a portion of this hierarchy showing research in
Software Visualization.
<P>
A major drawback of the World-Wide Web is that very few useful semantic attributes are
defined for the pages. To create some other meaningful hierarchies, attributes like the 
topic of the page (whether it is a research page or a personal page, etc.) were inserted 
manually. (Efforts are underway to incorporate metadata into WWW and hopefully in the near
future we can extract all useful information from the WWW automatically.) The left hand 
screen of Figure 9 represents a treemap view of a hierarchy formed when the initial 
partitioning is done by the topic of the page. The colors are used to represent the kind 
of users who created the pages. Green is used to represent Phd students and the color 
plate indicates that the Phd students are the primary authors of the pages. 
<P>
<!WA24><A HREF="http://www.cc.gatech.edu/gvu/people/Phd/sougata/chi95/sm_fg9.gif#map"> FIGURE 9: </A>
The left hand scree shows a Treemap view of a hierarchy of the GVU WWW pages. Initial
partitioning is by the attribute <em> Topic </em>. Colors represent different types of
authors. The selected node is <em> visdebug.html </em>. The corresponding WWW page is
shown on the right.
<P>
Multiple hierarchies, each giving a different perspective to the underlying information
space can be formed. If a user selects a node in one view, its positions in the other 
views are also highlighted. Thus, these views help the user in comprehending the data. It 
should be also noted that the user can go directly to the corresponding WWW page for the 
selected node.  Thus in the Treemap view, the node <em>visdebug.html</em> is highlighted. 
The corresponding WWW page is shown on the right hand screen of Figure 9.

<H2> GENERATING OTHER VIEWS</H2>
Once a hierarchy is formed from the original graph structure, the hierarchy can be 
transformed to other data organizations as well. Visualizations can be formed for these 
data organizations also. For example, if the original partitioning for forming the 
hierarchy was done by a quantitative attribute, a linear structure sorted by that 
attribute can be formed from the subtrees of the root node. 
<P>
Figure 10 represents a perspective wall <!WA25><A HREF="http://www.cc.gatech.edu/gvu/people/Phd/sougata/chi95/sm_bdy.html#Mac91">[9]</A> view of a 
linear arrangement of the GVU WWW pages sorted by the last modification times of the 
files. From the hierarchy whose initial partitioning was by the attribute 
<em>last-modified-time</em>, the files were divided into partitions based on the time when
they were last modified. These partitions were arranged on walls. Only some walls are in 
the focus at a given time. The user can easily control the walls which are in focus 
through a scrollbar. Similarly, for the automobile database a Perspective Wall view can be
formed where the cars are sorted by the attribute <em>Price</em>.
<P>
<!WA26><A HREF="http://www.cc.gatech.edu/gvu/people/Phd/sougata/chi95/sm_fg10.gif#wall"> FIGURE 10: </A>
A Perspective Wall view showing a linear arrangement of the files based on the last 
modification time. The different walls show files which were last modified in different 
time frames. Only some walls are in the focus at a given time.
<P>
Other views can also be generated. For example, a tabular view showing information like 
average price, mileage, etc. for various car models and also such useful statistics for 
different manufacturers of the cars can be formed  by a depth-first traversal of the 
hierarchical structure whose partitionings are done by the attributes 
<em>Manufacturer</em> and <em>Car-Model</em>.

<H2>RELATED WORK</H2>
Our structural analysis is similar to that described in <!WA27><A HREF="http://www.cc.gatech.edu/gvu/people/Phd/sougata/chi95/sm_bdy.html#Bot92">[2]</A>