GraphMaps: Browsing Large Graphs as Interactive Maps

Nachmanson, Lev and Prutkin, Roman and Lee, Bongshin and Riche, Nathalie Henry and Holroyd, Alexander E. and Chen, Xiaoji (2015) GraphMaps: Browsing Large Graphs as Interactive Maps. In: Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, September 24-26, 2015, Los Angeles, CA, USA , pp. 3-15 (Official URL: http://dx.doi.org/10.1007/978-3-319-27261-0_1).

Full text not available from this repository.

Abstract

Algorithms for laying out large graphs have seen significant progress in the past decade. However, browsing large graphs remains a challenge. Rendering thousands of graphical elements at once often results in a cluttered image, and navigating these elements naively can cause disorientation. To address this challenge we propose a method called GraphMaps, mimicking the browsing experience of online geographic maps. GraphMaps creates a sequence of layers, where each layer refines the previous one. During graph browsing, GraphMaps chooses the layer corresponding to the zoom level, and renders only those entities of the layer that intersect the current viewport. The result is that, regardless of the graph size, the number of entities rendered at each view does not exceed a predefined threshold, yet all graph elements can be explored by the standard zoom and pan operations. GraphMaps preprocesses a graph in such a way that during browsing, the geometry of the entities is stable, and the viewer is responsive. Our case studies indicate that GraphMaps is useful in gaining an overview of a large graph, and also in exploring a graph on a finer level of detail.

Item Type:Conference Paper
Classifications:M Methods > M.300 Dynamic / Incremental / Online
S Software and Systems > S.120 Visualization
ID Code:1472

Repository Staff Only: item control page

References

Abello, J., van Ham, F., Krishnan, N.: Ask-graphview: a large scale graph visualization system. IEEE Trans. Vis. Comput. Graph. 12(5), 669–676 (2006)

Abello, J., Kobourov, S.G., Yusufov, R.: Visualizing large graphs with compound-fisheye views and treemaps. In: Pach, J. (ed.) GD 2004. LNCS, vol. 3383, pp. 431–441. Springer, Heidelberg (2005)

Auber, D.: Using Strahler numbers for real time visual exploration of huge graphs. In: Computer Vision and Graphics (ICCVG’02), pp. 56–69 (2002)

Auber, D.: Tulip - a huge graph visualization framework. In: Graph Drawing Software, pp. 105–126 (2004)

Auber, D., Chiricota, Y., Jourdan, F., Melançon, G.: Multiscale visualization of small world networks. In: IEEE Symposium on Information Visualization (INFOVIS’03), pp. 75–81 (2003)

Balzer, M., Deussen, O.: Level-of-detail visualization of clustered graph layouts. In: Asia-Pacific Symposium on Information Visualisation (APVIS’07), pp. 133–140. IEEE (2007)

Bastian, M., Heymann, S., Jacomy, M.: Gephi: an open source software for exploring and manipulating networks. In: International AAAI Conference on Weblogs and Social Media (ICWSM’09) (2009)

Brandes, U.: A faster algorithm for betweenness centrality. J. Math. Sociol. 25(2), 163–177 (2001)

Brandes, U., Pich, C.: Eigensolver methods for progressive multidimensional scaling of large data. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol. 4372, pp. 42–53. Springer, Heidelberg (2007)

Brunel, E., Gemsa, A., Krug, M., Rutter, I., Wagner, D.: Generalizing geometric graphs. In: Speckmann, B. (ed.) GD 2011. LNCS, vol. 7034, pp. 179–190. Springer, Heidelberg (2011)

Eades, P., Feng, Q.-W.: Multilevel visualization of clustered graphs. In: North, S.C. (ed.) GD 1996. LNCS, vol. 1190, pp. 101–112. Springer, Heidelberg (1997)

van den Elzen, S., van Wijk, J.: Multivariate network exploration and presentation: from detail to overview via selections and aggregations. IEEE Trans. Vis. Comput. Graph. 20(12), 2310–2319 (2014)

Gansner, E.R., Koren, Y., North, S.C.: Topological fisheye views for visualizing large graphs. IEEE Trans. Vis. Comput. Graph. 11(4), 457–468 (2005)

Gansner, E., Hu, Y., Kobourov, S.: Gmap: visualizing graphs and clusters as maps. In: IEEE Pacific Visualization Symposium (PacificVis’10), pp. 201–208. IEEE (2010)

van Ham, F., van Wijk, J.: Interactive visualization of small world graphs. In: IEEE Symposium on Information Visualization (INFOVIS’04), pp. 199–206 (2004)

van Ham, F., Perer, A.: Search, show context, expand on demand: supporting large graph exploration with degree-of-interest. IEEE Trans. Vis. Comput. Graph. 15(6), 953–960 (2009)

Henry, N., Bezerianos, A., Fekete, J.D.: Improving the readability of clustered social networks using node duplication. IEEE Trans. Vis. Comput. Graph. 14(6), 1317–1324 (2008)

Henry, N., Fekete, J.D., McGuffin, M.J.: NodeTrix: a hybrid visualization of social networks. IEEE Trans. Vis. Comput. Graph. 13(6), 1302–1309 (2007)

Nachmanson, L., Prutkin, R., Lee, B., Riche, N.H., Holroyd, A.E., Chen, X.: Graphmaps: Browsing large graphs as interactive maps. CoRR arXiv:​1506.​06745 (2015)

Nocaj, A., Ortmann, M., Brandes, U.: Untangling hairballs. In: Duncan, C., Symvonis, A. (eds.) GD 2014. LNCS, vol. 8871, pp. 101–112. Springer, Heidelberg (2014)

Page, L., Brin, S., Motwani, R., Winograd, T.: The PageRank citation ranking: Bringing order to the web. Technical report 1999–66, Stanford InfoLab (1999)

Perer, A., Shneiderman, B.: Balancing systematic and flexible exploration of social networks. IEEE Trans. Vis. Comput. Graph. 12(5), 693–700 (2006)

Shewchuk, J.R.: Delaunay refinement algorithms for triangular mesh generation. Comput. Geom. Theory Appl. 22(1–3), 21–74 (2002)

Traud, A.L., Kelsic, E.D., Mucha, P.J., Porter, M.A.: Comparing community structure to characteristics in online collegiate social networks. SIAM Rev. 53(3), 526–543 (2011)

Wu, H.-Y., Takahashi, S., Lin, C.-C., Yen, H.-C.: A zone-based approach for placing annotation labels on metro maps. In: Dickmann, L., Volkmann, G., Malaka, R., Boll, S., Krüger, A., Olivier, P. (eds.) SG 2011. LNCS, vol. 6815, pp. 91–102. Springer, Heidelberg (2011)

Zinsmaier, M., Brandes, U., Deussen, O., Strobelt, H.: Interactive level-of-detail rendering of large graphs. IEEE Trans. Vis. Comput. Graph. 18(12), 2486–2495 (2012)