📄 http:^^www.cc.gatech.edu^gvu^people^phd^sougata^chi95^sm_bdy.html
字号:
Date: Wed, 15 Jan 1997 01:44:45 GMT
Server: Apache/1.1.1
Content-type: text/html
Content-length: 28864
Last-modified: Wed, 01 Mar 1995 18:10:17 GMT
<HEADER><TITLE>Visualizing Complex Hypermedia Networks through Multiple Hierarchical Views</TITLE></HEADER><BODY><H1>Visualizing Complex Hypermedia Networks through Multiple Hierarchical Views</H1><P><B>Sougata Mukherjea, James D. Foley, Scott Hudson</B><DL><DT>Graphics, Visualization & Usability Center<DT>College of Computing <DT>Georgia Institute of Technology<DT>E-mail: sougata@cc.gatech.edu, foley@cc.gatech.edu, hudson@cc.gatech.edu<BR></DL><P> <DL><DT> <B>ABSTRACT:</B><DD>Our work concerns visualizing the information space of hypermedia systems usingmultiple hierarchical views. Although overview diagrams are useful for helping the user tonavigate in a hypermedia system, for any real-world system they become too complicated and large to be really useful. This is because these diagrams represent complex network structures which are very difficult to visualize and comprehend. On the other hand, effective visualizations of hierarchies have been developed. Our strategy is to providethe user with different hierarchies, each giving a different perspective to the underlyinginformation space to help the user better comprehend the information. We propose an algorithm based on content and structural analysis to form hierarchies from hypermedia networks. The algorithm is automatic but can be guided by the user. The multiple hierarchies can be visualized in various ways. We give examples of the implementation of the algorithm on two hypermedia systems.<DT> <B>KEYWORDS:</B><DD> Hypermedia, Overview Diagrams, Information Visualization, Hierarchization.</DL><H2> INTRODUCTION </H2>Overview diagrams are one of the best tools for orientation and navigation in hypermedia documents <!WA0><A HREF="http://www.cc.gatech.edu/gvu/people/Phd/sougata/chi95/sm_bdy.html#Utt89">[17]</A>. By presenting a map of the underlying information space, they allow the users to see where they are, what other information is available and how to access the other information. However, for any real-world hypermediasystem with many nodes and links, the overview diagrams represent large complex network structures. They are generally shown as 2D or 3D graphs and comprehending such large complex graphs is extremely difficult. The layout of graphs is also a very difficult problem <!WA1><A HREF="http://www.cc.gatech.edu/gvu/people/Phd/sougata/chi95/sm_bdy.html#Bat93">[1]</A>. Other attempts to visualize networks such as Semnet <!WA2><A HREF="http://www.cc.gatech.edu/gvu/people/Phd/sougata/chi95/sm_bdy.html#Fai88">[3]</A>, have not been very successful.<P>In <!WA3><A HREF="http://www.cc.gatech.edu/gvu/people/Phd/sougata/chi95/sm_bdy.html#Par89">[13]</A>, Parunak notes that: "The insight for hypermedia isthat 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." Neuwirth et al. <!WA4><A HREF="http://www.cc.gatech.edu/gvu/people/Phd/sougata/chi95/sm_bdy.html#Neu87">[12]</A> also observed that the ability to view knowledge from different perspectives is important. Thus, if different hierarchies, each of which gives a different perspective to the underlying information canbe formed, the user would be able to comprehend the information better. It should be also noted that unlike networks some very effective ways of visualizing hierarchies have been developed. Examples are <em>Treemaps</em> <!WA5><A HREF="http://www.cc.gatech.edu/gvu/people/Phd/sougata/chi95/sm_bdy.html#Joh91">[7]</A> and <em>Cone Trees</em> <!WA6><A HREF="http://www.cc.gatech.edu/gvu/people/Phd/sougata/chi95/sm_bdy.html#Rob91">[15]</A>.<P>This paper proposes an algorithm for forming hierarchies from hypermedia graphs. It usesboth structural and content analysis to identify the hierarchies. The structural analysislooks at the structure of the graph while the content analysis looks at the contents of the nodes. (Note that the content analysis assumes a database-oriented hypermedia systemwhere the nodes are described with attributes). Although our algorithm is automatic, forming the "best" possible hierarchy representing the graph, the user can guide the process so that hierarchies giving different perspectives to the underlying information can be formed. These hierarchies can be visualized in different ways.<P>Section 2 presents our hierarchization process. Section 3 shows the implementation of the algorithm in the <b>Navigational View Builder</b>, a system we are building for visualizing the information space of Hypermedia systems <!WA7><A HREF="http://www.cc.gatech.edu/gvu/people/Phd/sougata/chi95/sm_bdy.html#Muk94a">[10]</A>, <!WA8><A HREF="http://www.cc.gatech.edu/gvu/people/Phd/sougata/chi95/sm_bdy.htm#Muk94b">[11]</A>. This sectiondiscusses the application of the algorithm on a demo automobile database and a section of the <em>World-Wide Web</em>. Section 4 discusses how the hierarchies can be transformed toother forms of data organizations. Section 5 talks about the related work while section 6 is the conclusion.<H2>THE HIERARCHIZATION PROCESS</H2><H2>New Data Structure</H2>For our hierarchization process we use a data structure which we call the <b>pre-tree</b>.A pre-tree is an intermediate between a graph and a tree. It has a node called the <em>root</em> which does not have any parent node. However, unlike a real tree, all its descendants need not be trees themselves - they may be any arbitrary graph. Thesedescendants thus form a list of graphs and are called <em>branches</em>. However, there isone restriction - nodes from different branches cannot have links between them. Anexample pre-tree is shown in Figure 1. Note that pre-tree is another data structure like <em>multi-trees</em> <!WA9><A HREF="http://www.cc.gatech.edu/gvu/people/Phd/sougata/chi95/sm_bdy.html#Fur94">[4]</A> - it is not as complex as a graph but not as simple as a tree. Also note that although the term ``pre-tree'' has not been used before, this data structure has a long history in top-down clustering techniques <!WA10><A HREF="http://www.cc.gatech.edu/gvu/people/Phd/sougata/chi95/sm_bdy.html#Har75">[5]</A>. Top-down clustering would often be halted when new divisions were not auspicious, leaving a final structure which is essentially a pre-tree.<P><!WA11><A HREF="http://www.cc.gatech.edu/gvu/people/Phd/sougata/chi95/sm_fg1.gif#pretree"> FIGURE 1: </A>An example pre-tree. It has a root node which does not have any parent. Thedescendants of the root node are graphs. However, none of these graphs have any linksbetween them. Our hierarchization algorithm tries to identify the best pre-tree to represent the given graph. The final tree is formed by calling the algorithm recursivelyfor the branches.<H2>Hierarchization Algorithm</H2>The algorithm tries to identify a suitable pre-tree from a given graph. Thus a root node is identified and the other nodes are partitioned into branches. This root node forms the root of the final hierarchy. The algorithm is recursively called for each of the branches and the trees formed by these recursive calls become children of the root of the final hierarchy. The recursion stops if a branch has very few nodes or the required depth of thefinal tree has been reached. It may also happen that for certain branches, no suitablepre-trees can be formed. In these cases, the nodes of the branches become children of the parent of the branch. (This case generally occurs for branches with very few nodes). <P>For identifying potential pre-trees both content and structural analysis are used.<UL><LI> <em>Content analysis:</em> <P>For content analysis, for each attribute, the nodes of the graph are partitioned into branches based on the attribute values by <em>Content-based Clustering</em>. The clustering algorithm is explained in <!WA12><A HREF="http://www.cc.gatech.edu/gvu/people/Phd/sougata/chi95/sm_bdy.html#Muk94b">[11]</A>. If too many or too few branches are formed, the attribute is not suitable for forming a pre-tree. Otherwise a new pre-tree is formed with these branches. The root of the pre-tree is a <em>cluster</em> representing all the nodes of the graph.<P><LI> <em>Structural analysis:</em> <P>A pre-tree is formed for nodes in the graph which can reach all other nodes. These nodes are designated as the roots of the pre-trees. The branches are the branches of the spanning tree formed by doing a breadth-first search from the designated root node. (Adetailed analysis is omitted for the purpose of brevity. The algorithm is explained withexamples in the next section).</UL>Both content and structural analysis can identify several potential pre-trees. A <em>metric</em> is used to rank these pre-trees. The metric consists of the following submetrics:<UL><LI> Information lost in the formation of the pre-tree: When the nodes are partitioned for forming the branches, all links joining nodes in different branches are removed. Thus valuable information is lost and a submetric calculates the ratio of the number of links remaining in the branches to the total number of links in the original graph to rank the pre-trees in order of the least amount of information lost.<LI> "Treeness" of the branches: Since our overall objective is to form trees, it isadvantageous if the branches of the pre-tree are already close to trees. If all thebranches only consisted of trees, there would be a total of <em> n - c </em> links where <em>n</em> is the total number of nodes in the branches and <em>c</em> is the number ofconnected components. Thus a submetric which calculates the ratio <em>(n-c)/l</em>where <em>l</em> is the total number of links is an indication of the "treeness" of the branches.<LI> "Goodness" of the root: For a structural pre-tree the goodness of the root is determined by the sum of the distances of the shortest path from the root to all other nodes. A "good" root will reach all other nodes by following only a few links so that the resulting tree is not very deep. A deep tree is not desirable since it will force theuser to follow a long and tedious path to reach some information. For content analysis thegoodness of the root is determined by the relevance of the attribute. (For example, for anautomobile database, the manufacturer of the cars is a more relevant attribute than the number of doors of the cars).</UL>Each submetric returns a number between 0 and 1. The overall metric is calculated by aweighted sum of the submetrics where the weight is determined by the relative importance of the submetrics.<P><H2>The Role of the User</H2>By default, the entire process would be automatically forming the "best" hierarchical form for the original graph. However, the user can guide the process both during the ⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -