A Simplification Algorithm for Visualizing the Structure of Complex Graphs

D. Hennessey, D. Brooks, A. Fridman and D. Breen, ``A Simplification Algorithm for Visualizing the Structure of Complex Graphs,'' Proceedings of 12th International Conference on Information Visualisation, July 2008, pp. 619 - 629.

Complex graphs, ones containing thousands of nodes of high degree, are difficult to visualize. Displaying all of the nodes and edges of these graphs can create an incomprehensible cluttered output. This paper presents a simplification algorithm that may be applied to a complex graph in order to produce a controlled thinning of the graph. Using importance metrics, the simplification process removes nodes from the graph, leaving the central structure for visualization and evaluation. The simplification algorithm consists of two steps, calculation of the importance metrics and pruning. Several metrics based on various topological graph properties are described. The metrics are then used in a pruning process to simplify the graph. Nodes, along with their corresponding edges, are removed from the graph, while maintaining the graph's overall connectivity. This simplificleaner, more meaningful visual representation of the graph's structure; thus aiding the analysis of the graph's underlying data.

Last modified on July 11, 2008.