| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Visual Exploration of Complex Time-Varying Graphs
September-October 2006 (vol. 12 no. 5)
pp. 805-812
Many graph drawing and visualization algorithms, such as force-directed layout and line-dot rendering, work very well on relatively small and sparse graphs. However, they often produce extremely tangled results and exhibit impractical running times for highly non-planar graphs with large edge density. And very few graph layout algorithms support dynamic time-varying graphs; applying them independently to each frame produces distracting temporally incoherent visualizations. We have developed a new visualization technique based on a novel approach to hierarchically structuring dense graphs via stratification. Using this structure, we formulate a hierarchical force-directed layout algorithm that is both efficient and produces quality graph layouts. The stratification of the graph also allows us to present views of the data that abstract away many small details of its structure. Rather than displaying all edges and nodes at once, resulting in a convoluted rendering, we present an interactive tool that filters edges and nodes using the graph hierarchy and allows users to drill down into the graph for details. Our layout algorithm also accommodates time-varying graphs in a natural way, producing a temporally coherent animation that can be used to analyze and extract trends from dynamic graph data. For example, we demonstrate the use of our method to explore financial correlation data for the U.S. stock market in the period from 1990 to 2005. The user can easily analyze the time-varying correlation graph of the market, uncovering information such as market sector trends, representative stocks for portfolio construction, and the interrelationship of stocks over time.
[1] 805 R. Andersen, F. Chung, and L. Lu, Drawing power law graphs using a local/global decomposition, 2004.[2] V. Boginski, S. Butenko, and P. M. Pardalos, On structural properties of the market graph. Innovations in Financial and Economic Networks, pages 29–45, 2003.[3] V. Boginski, S. Butenko, and P. M. Pardalos, Statistical analysis of financial networks. Computational Statistics and Data Analysis, 48 (2): 431–443, 2005.[4] D. S. Chan, K. S. Chua, C. Leckie, and A. Parhar, Visualisation of powerlaw network topologies. In Proc. of the 11th IEEE Intl. Conf. on Networks, pages 69–74, 2003.[5] M. Dickerson, D. Eppstein, M. T. Goodrich, and J. Meng, Confluent drawings: Visualizing non-planar diagrams in a planar way. In Proc. 11th Int'l Symp. on Graph Drawing, pages 1–12, 2002.[6] D. P. Dobkin, A. Hausner, E. R. Gansner, and S. C. North, Uncluttering force-directed graph layouts. In Proc. of the 15th Symp. on Computational Geometry, pages 425–426, 1999.[7] Q. Du, V. Faber, and M. Gunzburger, Centroidal voronoi tessellations: Applications and algorithms. SIAM Review, 41 (4): 637–676, 1999.[8] P. Eades, A heuristic for graph drawing. Congressus Numerantium, 42: 149–160, 1984.[9] L. C. Freeman, Visualizing social networks. Journal of Social Structure, 1 (1), 2000.[10] T. M. J. Fruchterman and E. M. Reingold, Graph drawing by forcedirected placement. Software: Practice and Experience, 21 (11): 1129–1164, 1991.[11] E. Gansner, Y. Koren, and S. North, Topological fisheye views for visualizing large graphs. In Proc. of the IEEE Symp. on Information Visualization, pages 175–182, 2004.[12] E. R. Gansner and S. C. North, Improved force-directed layouts. In Proc. 6th Int'l Symp. on Graph Drawing, pages 364–373, 1998.[13] C. Gorg, P. Birke, M. Pohl, and S. Diehl, Dynamic graph drawing of sequences of orthogonal and hierarchical graphs. In Proc. 12th Int'l Symp. on Graph Drawing, pages 228–238, 2004.[14] S. Hachul and M. Junger, Drawing large graphs with a potential-fieldbased multilevel algorithm. In Proc. of the 12th Intl. Symp. on Graph Drawing, pages 285–295, 2004.[15] D. Harel and Y. Koren, A fast multi-scale method for drawing large graphs. In Proc. 8th Int'l Symp. on Graph Drawing, pages 183–196, 2000.[16] T. Kamada and S. Kawai, An algorithm for drawing general undirected graphs. Information Processing Letters, 31 (1): 7–15, 1989.[17] J. M. Kleinberg, Authoritative sources in a hyperlinked environment. Journal of the ACM, 46 (5): 604–632, 1999.[18] H. Markowitz, Portfolio selection. J. of Finance, 7 (1): 77–91, 1952.[19] M. E. J. Newman, Fast algorithm for detecting community structure in networks. Physical Review E, 69 (1):066133, 2004.[20] S. C. North, Incremental layout in dynadag. In Proc. of Graph Drawing '95, volume 1027, pages 409–418, 1996.[21] J-P Onnela, A. Chakraborti, K. Kaski, J. Kertesz, and A. Kanto, Dynamics of market correlations: Taxonomy and portfolio analysis. Physical Review E, 68:056110, 2003.[22] K. J. Pulo, Recursive space decompositions in force-directed graph drawing algorithms. In Proc. of Australian Symp. on Information Visualisation, pages 95–102, 2001.[23] B. Schneiderman, The eyes have it: A task by data type taxonomy for information visualization. In Proc. for IEEE Symp. on Visual Languages, pages 336–343, 1996.[24] F. van Ham and J. J. van Wijk, Interactive visualization of small world graphs. In Proc. of the IEEE Symp. on Information Visualization, pages 199–206, 2004.[25] A. Y. Wu, M. Garland, and J. Han, Mining scale-free networks using geodesic clustering. In Proc. of the 10th Intl. Conf. on Knowledge Discovery and Data Mining, pages 719–724, 2004.
Index Terms:
Graph and network visualization, financial data visualization, hierarchy visualization, time series data
Citation:
Gautam Kumar, Michael Garland, "Visual Exploration of Complex Time-Varying Graphs," IEEE Transactions on Visualization and Computer Graphics, vol. 12, no. 5, pp. 805-812, Sept. 2006, doi:10.1109/TVCG.2006.193
