Abstract
In this paper, we present a new approach to exploring dynamic graphs. We have developed a new clustering algorithm for dynamic graphs which finds an ideal clustering for each time-step and links the clusters together. The resulting time-varying clusters are then used to define two visual representations. The first view is an overview that shows how clusters evolve over time and provides an interface to find and select interesting time-steps. The second view consists of a node link diagram of a selected time-step which uses the clustering to efficiently define the layout. By using the time-dependant clustering, we ensure the stability of our visualization and preserve user mental map by minimizing node motion, while simultaneously producing an ideal layout for each time step. Also, as the clustering is computed ahead of time, the second view updates in linear time which allows for interactivity even for graphs with upwards of tens of thousands of nodes.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Abello, J., van Ham, F., Krishnan, N.: ASK-GraphView: A large scale graph visualization system. IEEE TVCG 12(5), 669–676 (2006)
Archambault, D., Munzner, T., Auber, D.: GrouseFlocks: Steerable exploration of graph hierarchy space. IEEE TVCG 14(4), 900–913 (2008)
Archambault, D., Purchase, H.C., Pinaud, B.: Animation, small multiples, and the effect of mental map preservation in dynamic graphs. IEEE TVCG 17(4), 539–552 (2011)
Blondel, V., Guillaume, J., Lambiotte, R., Lefebvre, E.: Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment (2008)
Boitmanis, K., Brandes, U., Pich, C.: Visualizing Internet Evolution on the Autonomous Systems Level. In: Hong, S.-H., Nishizeki, T., Quan, W. (eds.) GD 2007. LNCS, vol. 4875, pp. 365–376. Springer, Heidelberg (2008)
Brandes, U., Delling, D., Gaertler, M., Goerke, R., Hoefer, M., Nikoloski, Z., Wagner, D.: Maximizing modularity is hard (2006), http://arxiv.org/abs/physics/0608255
Brandes, U., Mader, M.: A Quantitative Comparison of Stress-Minimization Approaches for Offline Dynamic Graph Drawing. In: van Kreveld, M., Speckmann, B. (eds.) GD 2011. LNCS, vol. 7034, pp. 99–110. Springer, Heidelberg (2011)
Burch, M., Vehlow, C., Beck, F., Diehl, S., Weiskopf, D.: Parallel edge splatting for scalable dynamic graph visualization. IEEE TVCG 17(12), 2344–2353 (2011)
Diehl, S., Görg, C.: Graphs, They are Changing: Dynamic Graph Drawing for a Sequence of Graphs. In: Goodrich, M.T., Kobourov, S.G. (eds.) GD 2002. LNCS, vol. 2528, pp. 23–30. Springer, Heidelberg (2002)
Erten, C., Harding, P.J., Kobourov, S.G., Wampler, K., Yee, G.: GraphAEL: Graph Animations with Evolving Layouts. In: Liotta, G. (ed.) GD 2003. LNCS, vol. 2912, pp. 98–110. Springer, Heidelberg (2004)
Frishman, Y., Tal, A.: Online dynamic graph drawing. IEEE TVCG 14(4), 727–740 (2008)
Garey, M.R., Johnson, D.S.: Computers and Intractability: a Guide to the Theory of NP-Completeness. W. H. Freeman (1979)
Görg, C., Birke, P., Pohl, M., Diehl, S.: Dynamic Graph Drawing of Sequences of Orthogonal and Hierarchical Graphs. In: Pach, J. (ed.) GD 2004. LNCS, vol. 3383, pp. 228–238. Springer, Heidelberg (2004)
Hachul, S., Jünger, M.: An Experimental Comparison of Fast Algorithms for Drawing General Large Graphs. In: Healy, P., Nikolov, N.S. (eds.) GD 2005. LNCS, vol. 3843, pp. 235–250. Springer, Heidelberg (2006)
van Ham, F., van Wijk, J.J.: Interactive visualization of small world graphs. In: Proceedings of the IEEE Symposium on Information Visualization (InfoVis 2004), pp. 199–206 (2004)
Haverkort, H.J., van Walderveen, F.: Locality and bounding-box quality of two-dimensional space-filling curves. Computational Geometry, Theory and Applications 43(2), 131–147 (2010)
Holten, D.: Hierarchical edge bundles: Visualization of adjacency relations in hierarchical data. IEEE TVCG 12(5), 741–748 (2006)
Hu, Y., Kobourov, S.G., Veeramoni, S.: Embedding, clustering and coloring for dynamic maps. In: Proceedings of the 5th IEEE Pacific Visualization Symposium (PacificVis 2012), pp. 33–40 (2012)
Koren, Y., Harel, D.: A Multi-scale Algorithm for the Linear Arrangement Problem. In: Kučera, L. (ed.) WG 2002. LNCS, vol. 2573, pp. 296–309. Springer, Heidelberg (2002)
Kumar, G., Garland, M.: Visual exploration of complex time-varying graphs. IEEE TVCG 12(5), 805–812 (2006)
Muelder, C., Ma, K.L.: Rapid graph layout using space filling curves. IEEE TVCG 14(6), 1301–1308 (2008)
Newman, M.E.J., Girvan, M.: Graph clustering. Physical Review E 69(026113) (2004)
Noack, A.: Modularity clustering is force-directed layout. CoRR abs/0807.4052 (2008)
North, S.C.: Incremental Layout in DynaDAG. In: Brandenburg, F.J. (ed.) GD 1995. LNCS, vol. 1027, pp. 409–418. Springer, Heidelberg (1996)
Ogawa, M., Ma, K.L.: Software evolution storylines. In: Proceedings of the ACM 2010 Symposium on Software Visualization (SoftVis 2010), pp. 35–42 (2010)
Petit, J.: Experiments on the minimum linear arrangement problem. Tech. Rep. LSI-01-7-R, Universitat Politecnica de Catalunya, Departament de Llenguatges i Sistemes Informatics (2001)
Purchase, H.C., Hoggan, E., Görg, C.: How Important Is the “Mental Map”? – An Empirical Investigation of a Dynamic Graph Layout Algorithm. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol. 4372, pp. 184–195. Springer, Heidelberg (2007)
Purchase, H.C., Samra, A.: Extremes Are Better: Investigating Mental Map Preservation in Dynamic Graphs. In: Stapleton, G., Howse, J., Lee, J. (eds.) Diagrams 2008. LNCS (LNAI), vol. 5223, pp. 60–73. Springer, Heidelberg (2008)
Saffrey, P., Purchase, H.: The ”mental map” versus ”static aesthetic” compromise in dynamic graphs: A user study. In: Proceedings of the 9th Australasian User Interface Conference (AUIC 2008), pp. 85–93 (2008)
Schaeffer, S.E.: Graph clustering. Computer Science Review 1(1), 27–64 (2007)
Tanahashi, Y., Ma, K.L.: Design considerations for optimizing storyline visualizations. To appear in IEEE TVCG (2012)
Tufte, E.R.: Envisionning Information. Graphics Press (1990)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sallaberry, A., Muelder, C., Ma, KL. (2013). Clustering, Visualizing, and Navigating for Large Dynamic Graphs. In: Didimo, W., Patrignani, M. (eds) Graph Drawing. GD 2012. Lecture Notes in Computer Science, vol 7704. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-36763-2_43
Download citation
DOI: https://doi.org/10.1007/978-3-642-36763-2_43
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-36762-5
Online ISBN: 978-3-642-36763-2
eBook Packages: Computer ScienceComputer Science (R0)