An LOD model for graph visualization and its application in web navigation

Abstract

This paper presents a new method for visualizing and navigating huge graphs. The main feature of this method is that it applies Level-Of-Detail (LOD) strategy to graph visualization and navigation, and allows the user to navigate the graph in real time. First, the algorithm calculates the weight for each vertex by an improved link analysis method. Second, representative vertices with higher weights are selected. Third, a wavefront algorithm is utilized to cluster neighboring vertices for each representative vertex. This step produces several clusters characterized by the representative vertices. Then steps two and three are repeated in each cluster to form an LOD tree. Finally, we use a force-directed method to draw the sub-graph under the non-leaf node of the LOD tree. Based on the proposed method, we develop a graph visualization and navigation system - DynamicViewer. We then demonstrate its application in Web navigation. With DynamicViewer, the user can have an overview of the Web and then browse individual information on demand. The experiment results show that DynamicViewer enhances the ability to provide the right information to the user. © Springer-Verlag Berlin Heidelberg 2005.