Clustering, Visualizing, and Navigating for Large Dynamic Graphs

Sallaberry, Arnaud and Muelder, Chris and Ma, Kwan-Liu (2013) Clustering, Visualizing, and Navigating for Large Dynamic Graphs. In: 20th International Symposium, GD 2012, September 19-21, 2012, Redmond, WA, USA , pp. 487-498 (Official URL:

Full text not available from this repository.


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.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-36763-2_43
Classifications:M Methods > M.300 Dynamic / Incremental / Online
P Styles > P.720 Straight-line
P Styles > P.999 Others
S Software and Systems > S.120 Visualization
ID Code:1336

Repository Staff Only: item control page


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),

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)