How to cite this WIREs title:
WIREs Comp Stat

Visualizing large graphs

Advanced Review

Yifan Hu, Lei Shi

Published Online: Jan 12 2015

DOI: 10.1002/wics.1343

Full article on Wiley Online Library: HTML PDF

Can't access this content? Tell your librarian.

With the prevalence of big data, there is a growing need for algorithms and techniques for visualizing very large and complex graphs. In this article, we review layout algorithms and interactive exploration techniques for large graphs. In addition, we briefly look at softwares and datasets for visualization graphs, as well as challenges that need to be addressed. WIREs Comput Stat 2015, 7:115–136. doi: 10.1002/wics.1343 This article is categorized under: Statistical Learning and Exploratory Methods of the Data Sciences > Exploratory Data Analysis Data: Types and Structure > Graph and Network Data Statistical and Graphical Methods of Data Analysis > Statistical Graphics and Visualization

An illustration of the quadtree data structure. Left: the overall quadtree. Right: supernodes with reference to a vertex at the top middle part of the graph, with θ = 1.

[ Normal View | Magnified View ]

Visualization of a small social network.

[ Normal View | Magnified View ]

Visualizations of an airline route graph. Left: Original layout. Right: Geometric edge bundling.

[ Normal View | Magnified View ]

Visualizations of a protein interaction graph: (a) Unsimplified; (b) Stochastic edge sampling; (c) Geodesic clustering; (d) Edge centrality based filtering.

[ Normal View | Magnified View ]

Large graph exploration through Degree‐of‐Interest diffusion. The data set is US legal document citation network.

[ Normal View | Magnified View ]

The five types of hierarchical abstraction based visualization. The interactive navigation methods on large graph visualization normally change the hierarchy setting within each type or switch between different types.

[ Normal View | Magnified View ]

Semantic and heterogeneous abstraction of large graphs. Left: PivotGraph of a communication network of people in a large company, x‐axis is division, y‐axis is office geography.¹⁰⁷ Right: OnionGraph of a host/domain‐user‐application network in a commodity Ethernet setting.

[ Normal View | Magnified View ]

Large graph visualizations through node clustering.,,,

[ Normal View | Magnified View ]

Motif simplification of a network of wiki edits.

[ Normal View | Magnified View ]

Lossless compression a small network traffic graph.

[ Normal View | Magnified View ]

Example drawings of large graphs.

[ Normal View | Magnified View ]

Result of some of the algorithms applied to two graphs, dw256A and qh882.

[ Normal View | Magnified View ]

An illustration of the edge collapsing‐based graph coarsening. Left: original graph with 85 vertices. Edges in a maximal independent edge set are thickened. Right: a coarser graph with 43 vertices resulted from coalescing thickened edges.

[ Normal View | Magnified View ]

References

Batagelj, V. Visualization of large networks. In: Meyers, RA, ed. Encyclopedia of Complexity and Systems Science. New York: Springer; 2009.
E Krujaa,, J Marks,, A Blair,, and R Waters,. A short note on the history of graph drawing. In: Proceedings of the 9th International Symposium Graph Drawing (GD`01), Vienna, Austria, 23–26 September, 2001. London: Springer‐Verlag; 2002, 272–286.
Tamassia, R. Handbook of Graph Drawing and Visualization. Chapman %26 Hall/CRC: 2013.
Tutte, W. How to draw a graph. Proc London Math Soc 1963, 13:743–768.
Eades, P. A heuristic for graph drawing. Congr Numer 1984, 42:149–160.
Fruchterman, TMJ, Reingold, EM. Graph drawing by force directed placement. Softw Pract Exper 1991, 21:1129–1164.
Kamada, T, Kawai, S. An algorithm for drawing general undirected graphs. Inf Proc Lett 1989, 31:7–15.
Brandes, U, Pich, C. Eigensolver methods for progressive multidimensional scaling of large data. In: Proceedings of the 14th International Symposium on Graph Drawing (GD`06), vol 4372 of Lect Notes Comput Sci, Karlsruhe, Germany, 18–20 September, 2006; 2007, 42–53.
Hachul, S, Jünger, M. Drawing large graphs with a potential field based multilevel algorithm. In: Proceedings of the 12th International Symposium on Graph Drawing (GD`04), vol 3383 of Lect Notes Comput Sci, Harlem, NY, USA, 29 September–2 October, 2004. Springer; 2004, 285–295.
Hu, Y. Efficient and high quality force‐directed graph drawing. Mathematica Journal 2005.
Quigley, A. Large‐scale relational information visualization, clustering, and abstraction. PhD Thesis, Department of Computer Science and Software Engineering, University of Newcastle, 2001.
Tunkelang, D. A numerical optimization approach to general graph drawing. PhD Thesis, Carnegie Mellon University, 1999.
Walshaw, C. A multilevel algorithm for force‐directed graph drawing. J Graph Algorithms Appl 2003, 7:253–285.
Gajer, P, Goodrich, MT, Kobourov, SG. A fast multi‐dimensional algorithm for drawing large graphs. Lect Notes Comput Sci 1984, 211–221:2000.
Harel, D, Koren, Y. A fast multi‐scale method for drawing large graphs. J Graph Algorithms Appl 2002, 6:179–202.
Watts, D, Strogate, S. Collective dynamics of “small‐world” networks. Nature 1998, 393:440–442.
Gansner, ER, Koren, Y, North, S. Topological fisheye views for visualizing large graphs. IEEE Trans Vis Comput Graph 2005, 11:457–468.
Quigley, A, Eades, P. FADE: graph drawing, clustering, and visual abstraction. Lect Notes Comput Sci 1984, 183–196:2000.
Dunne, C, Shneiderman, B. Motif simplification: improving network visualization readability with fan, connector, and clique glyphs. In: Proceedings of the International Conference on Human Factors in Computing Systems (CHI`13), Paris, France, 27 April–2 May, 2013, 3247–3256.
Dwyer, T, Riche, NH, Marriott, K, Mears, C. Edge compression techniques for visualization of dense directed graphs. IEEE Trans Vis Comput Graph 2013, 19:2596–2605.
Shi, L, Liao, Q, Sun, X, Chen, Y, Lin, C. Scalable network traffic visualization using compressed graphs. In: IEEE International Conference on Big Data, 2013, 606–612.
Herman, I, Melancon, G, Marshall, MS. Graph visualization and navigation in information visualization: a survey. IEEE Trans Vis Comput Graph 2000, 6:24–43.
Lamping, J, Rao, R, Pirolli, P. A focus+context technique based on hyperbolic geometry for visualizing large hierarchies. In: Sigchi Conference on Human Factors in Computing Systems (CHI `95), Denver, Colorado, USA, 7–11 May, 1995. ACM; 1995, 401–408.
Munzner, T, Burchard, P. Visualizing the structure of the world wide web in 3D hyperbolic space. In: Proceedings of the First Symposium on Virtual Reality Modeling Language (VRML`95). New York, NY. ACM; 1995, 33–38.
Munzner, T. Exploring large graphs in 3d hyperbolic space. IEEE Comput Graph Appl 1998, 18:18–23.
Noack, A. An energy model for visual graph clustering. In: Proceedings of the 11th International Symposium on Graph Drawing (GD`2003), vol 2912 of Lect Notes Comput Sci, Perugia, Italy, 21–24 September, 2003. Springer; 2004, 425–436.
Bruss, I, Frick, A. Fast interactive 3‐D graph visualization. Lect Notes Comput Sci 1995, 1027:99–11.
Barnes, J, Hut, P. A hierarchical O(NlogN) force‐calculation algorithm. Nature 1986, 324:446–449.
Pfalzner, S, Gibbon, P. Many‐Body Tree Methods in Physics. Cambridge: Cambridge University Press; 1996.
Burton, A, Field, AJ, To, HW. A cell‐cell Barnes Hut algorithm for fast particle simulation. Aust Comput Sci Commun 1998, 20:267–278.
Greengard, LF. The Rapid Evaluation of Potential Fields in Particle Systems. Cambridge, MA: MIT Press; 1988.
Gupta, A, Karypis, G, Kumar, V. Highly scalable parallel algorithms for sparse matrix factorization. IEEE Trans Parallel Distrib Syst 1997, 5:502–520.
Hendrickson, B, Leland, R. A multilevel algorithm for partitioning graphs. Technical Report SAND93‐1301. Allbuquerque, NM: Sandia National Laboratories, 1993.
Walshaw, C, Cross, M, Everett, MG. Parallel dynamic graph partitioning for adaptive unstructured meshes. J Parallel Distrib Comput 1997, 47:102–108.
Hu, Y, Scott, JA. A multilevel algorithm for wavefront reduction. SIAM J Sci Comput 2001, 23:1352–1375.
Safro, I, Ron, D, Brandt, A. Multilevel algorithms for linear ordering problems. J Exp Algorithmics 2009, 13:1.4–1.20.
Walshaw, C. A multilevel approach to the travelling salesman problem. Oper Res 2002, 50:862–877.
Walshaw, C. Multilevel refinement for combinatorial optimisation problems. Ann Oper Res 2004, 131:325–372.
Hadany, R, Harel, D. A multi‐scale algorithm for drawing graphs nicely. Discrete Appl Math 2001, 113:3–21.
Barnard, ST, Simon, HD. Fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems. Concurr Comput 1994, 6:101–117.
Bartel, G, Gutwenger, C, Klein, K, Mutzel, P. An experimental evaluation of multilevel layout methods. In: Proceedings of the 18th International Symposium on Graph Drawing (GD`10), Konstanz, Germany, 21–24 September, 2010. Springer; 2010, 80–91.
Davis, TA, Hu, Y. The University of Florida Sparse Matrix Collection. ACM Trans Math Softw 2011, 38:1–25.
Hu, Y. A gallery of large graphs. Available at: http://yifanhu.net/GALLERY/GRAPHS/.
Kruskal, JB. Multidimensioal scaling by optimizing goodness of fit to a nonmetric hypothesis. Psychometrika 1964, 29:1–27.
JB Kruskal, and JB Seery,. Designing network diagrams. In: Proceedings of the First General Conference on Social Graphics, Washington, DC, July 1980, 22–50. US Department of the Census Bell Laboratories Technical Report No 49.
Gansner, ER, Koren, Y, North, SC. Graph drawing by stress majorization. In: Proceedings of the 12th International Symposium on Graph Drawing (GD`04), vol 3383 of Lect Notes Comput Sci, Harlem, NY, USA, 29 September–2 October, 2004. Springer; 2004, 239–250.
Brandes, U, Pich, C. An experimental study on distance based graph drawing. In: Proceedings of the 16th International Symposium on Graph Drawing (GD`06), vol 5417 of Lect Notes Comput Sci, Karlsruhe, Germany, 18–20 September, 2006. Springer‐Verlag; 2009, 218–229.
Torgerson, WS. Multidimensional scaling: I. theory and method. Psychometrika 1952, 17:401–419.
Young, G, Householder, AS. Discussion of a set of points in terms of their mutual distances. Psychometrika 1938, 3:19–22.
de Silva, V, Tenenbaum, JB. Global versus local methods in nonlinear dimensionality reduction. In: Becker, S, Thrun, S, Obermayer, K, eds. Advances in Neural Information Processing Systems 15. Cambridge, MA: MIT Press; 2003, 721–728.
Gansner, ER, Hu, Y, North, SC. A maxent‐stress model for graph layout. IEEE Trans Vis Comput Graph 2013, 19:927–940.
Khoury, M, Hu, Y, Krishnan, S, Scheidegger, CE. Drawing large graphs by low‐rank stress majorization. Comput Graph Forum 2012.
Drineas, P, Frieze, AM, Kannan, R, Vempala, S, Vinay, V. Clustering large graphs via the singular value decomposition. Mach Learn 2004, 56:9–33.
Gansner, ER, Hu, Y, Krishnan, S. Coast: a convex optimization approach to stress‐based embedding. In: Wismath, S, Wolff, A, eds. Graph Drawing, vol 8242 of Lect Notes Comput Sci. Heidelberg, Germany: Springer; 2013, 268–279.
Harel, D, Koren, Y. High‐dimensional embedding. J Graph Algorithms Appl 2004, 8:195–214.
Hall, KM. An r‐dimensional quadratic placement algorithm. Manage Sci 1970, 17:219–229.
Y Koren,, L Carmel,, and D Harel,. Ace: a fast multiscale eigenvectors computation for drawing huge graphs. In INFOVIS `02: Proceedings of the IEEE Symposium on Information Visualization (InfoVis`02), Washington, DC, 2002, 137–144. IEEE Computer Society.
MDSJ. Multidimensional scaling for java. Available at: http://www.inf.uni‐konstanz.de/algo/software/mdsj/. (Accessed November 28, 2014).
Gansner, ER, North, S. An open graph visualization system and its applications to software engineering. Softw Pract Exper 2000, 30:1203–1233.
Gelphi. The open graph viz platform. Available at: https://gephi.github.io/. (Accessed November 28, 2014).
OGDF. Open graph drawing framework. http://www.ogdf.net/. (Accessed November 28, 2014).
Lorrain, F, White, HC. Structural equivalence of individuals in social networks. J Math Sociol 1971, 1:49–80.
van Ham, F, Wattenberg, M, Viegas, FB. Mapping text with phrase nets. IEEE Trans Vis Comput Graph 2009, 15:1169–1176.
Papadopoulos, C, Voglis, C. Drawing graphs using modular decomposition. J Graph Algorithms Appl 2007, 11:481–511.
Fortunato, S. Community detection in graphs. Phys Rep 2010, 486:75–174.
Newman, M. Modularity and community structure in networks. Proc Natl Acad Sci USA 2006, 103:8577–8582.
Han, J, Kamber, M. Data Mining: Concepts and Techniques. Morgan Kaufmann; 2001.
Auber, D, Chiricota, Y, Jourdan, F, Melancon, G. Multiscale visualization of small world networks. In: Proceedings of the IEEE Symposium on Information Visualization, Seattle, WA, 20–21 October, 2003, 75–81.
Abello, J, van Ham, F, Krishnan, N. ASK‐GraphView: a large scale graph visualization system. IEEE Trans Vis Comput Graph 2006, 12:669–676.
Shi, L, Cao, N, Liu, S, Qian, W, Tan, L, Wang, G, Sun, J, Lin, C‐Y. HiMap: adaptive visualization of large‐scale online social networks. In: Proceedings of the IEEE Pacific Visualization Symposium, Beijing, China, 20–23 April, 2009, 41–48.
Gansner, E, Hu, Y, North, S, Scheidegger, C. Multilevel agglomerative edge bundling for visualizing large graphs. In: Proceedings of IEEE Pacific Visualization Symposium, Hong Kong, 1–4 March, 2011, 187–194.
Holten, D. Hierarchical edge bundles: visualization of adjacency relations in hierarchical data. IEEE Trans Vis Comput Graph 2006, 12:741–748.
Lambert, A, Bourqui, R, Auber, D. Winding Roads: Routing edges into bundles. Comput Graph Forum 2010, 29:853–862.
Cui, W, Zhou, H, Qu, H, Wong, PC, Li, X. Geometry‐based edge clustering for graph visualization. IEEE Trans Vis Comput Graph 2008, 14:1277–1284.
J Lamping,, R Rao,, and P Pirolli,. A focus+context technique based on hyperbolic geometry for visualizing large hierarchies. In: Proceedings of the International Conference on Human Factors In Computing Systems (CHI`95), Denver, CO, 7–11 May, 1995.
Gansner, E, Koren, Y, North, S. Topological fisheye views for visualizing large graphs. In: IEEE Symposium on Information Visualization (InfoVis`04), Austin, TX, 10–12 October, 2004.
Jia, Y, Hoberock, J, Garland, M, Hart, JC. On the visualization of social and other scale‐free networks. IEEE Trans Vis Comput Graph 2008, 14:1285–1292.
van Ham, F, Wattenberg, M. Centrality based visualization of small world graphs. Comput Graph Forum 2008, 27:975–982.
M Wattenberg,. Visual exploration of multivariate graphs. In: Proceedings of the International Conference on Human Factors in Computing Systems (CHI`06), Montreal, Quebec, Canada, 22–27 April, 2006, 811–819.
Shen, Z, Ma, K‐L, Eliassi‐Rad, T. Visual analysis of large heterogeneous social networks by semantic and structural abstraction. IEEE Trans Vis Comput Graph 2006, 12:1427–1439.
Shi, L, Liao, Q, Tong, H, Hu, Y, Zhao, Y, Lin, C. Hierarchical focus + context heterogeneous network visualization. In: Proceedings of the IEEE Pacific Visualization Symposium, Yokohama, Japan, 4–7 March, 2014.
Elmqvist, N, Fekete, J‐D. Hierarchical aggregation for information visualization: Overview, techniques and design guidelines. IEEE Trans Vis Comput Graph 2010, 16:439–454.
Archambault, D, Munzner, T, Auber, D. Grouseflocks: Steerable exploration of graph hierarchy space. IEEE Trans Vis Comput Graph 2008, 14:900–913.
van Ham, F, Perer, A. “Search, Show Context, Expand on Demand”: supporting large graph exploration with degree‐of‐interest. IEEE Trans Vis Comput Graph 2009, 15:953–960.
T von Landesberger,, A Kuijper,, T Schreck,, J Kohlhammer,, JJ van Wijk,, J‐D Fekete,, and DW Fellner,. Visual analysis of large graphs. Comput Graph Forum 2011, 30:1719–1749.
Cytoscape. An open source platform for complex network analysis and visualization. Available at: http://www.cytoscape.org/.
Tulip. Data visualization software. Available at: http://www.cytoscape.org/. (Accessed November 28, 2014).
Dwyer, T, Marriott, K, Wybrow, M. Dunnart: A constraint‐based network diagram authoring tool. In: Tollis, I, Patrignani, M, eds. Graph Drawing, vol. 5417 of Lect Notes Comput Sci. Berlin/Heidelberg: Springer; 2009, 420–431.
D3.js. Data‐driven documents. Available at: http://d3js.org/. (Accessed November 28, 2014).
snap. Stanford large network dataset collection. Available at: http://snap.stanford.edu/data. (Accessed November 2014)
Koblenz. The koblenz network collection. Available at: http://konect.uni‐koblenz.de. (Accessed November 28, 2014).
GraphArchive. Exchange and archive system for graphs. Available at: http://www.graph‐archive.org/. (Accessed November 28, 2014).
House of Graphs. A database of interesting graphs. Available at: https://hog.grinvin.org/. (Accessed November 28, 2014).
Leskovec, J, Lang, K, Dasgupta, A, Mahoney, M. Community structure in large networks: natural cluster sizes and the absence of large well‐defined clusters. Internet Math 2009, 6:29–123.
Auber, D, Chiricota, Y. Improved efficiency of spring embedders: taking advantage of GPU programming. In: 7th IASTED International Conference on Visualization, Imaging and Image Processing, Palma de Mallorca, Spain, 29–31 August, 2007. ACTA Press; 2007, 169–175.
Monien, FRB, Salmen, H. A parallel simulated annealing algorithm for generating 3d layouts of undirected graphs. In: Proceedings of the 3th International Symposium on Graph Drawing (GD`95), vol 1027 of Lect Notes Comput Sci, Passau, Germany, 20–22 September, 1995. Springer‐Verlag; 1995, 90–101.
Frishman, Y, Tal, A. Multi‐level graph layout on the gpu. IEEE Trans Vis Comput Graph 2007, 13:1310–1319.
Ingram, S, Munzner, T, Olano, M. Glimmer: Multilevel mds on the gpu. IEEE Trans Vis Comput Graph 2009, 15:249–261.
Frishman, Y, Tal, A. Online dynamic graph drawing. In: Proceedings of Eurographics/IEEE VGTC Symposium on Visualization (EuroVis), Norrköping, Sweden, 23–25 May, 2007, 75–82.
Brandes, U, Mader, M. A quantitative comparison of stress‐minimization approaches for offline dynamic graph drawing. In: van Kreveld, MJ, Speckmann, B, eds. Graph Drawing, vol. 7034 of Lect Notes Comput Sci. Springer; 2011, 99–110.
L Shi,, C Wang,, Z Wen,, H Qu,, C Lin,, and Q Liao,. 1.5d egocentric dynamic network. IEEE Trans Vis Comput Graph, Submitted for publication.
Misue, K, Eades, P, Lai, W, Sugiyama, K. Layout adjustment and the mental map. J Vis Lang Comput 1995, 6:183–210.
Akoglu, L, McGlohon, M, Faloutsos, C. Oddball: spotting anomalies in weighted graphs. In: Proceedings of the 14th Pacific‐Asia Conference on Advances in Knowledge Discovery and Data Mining (PAKDD 2010), Hyderabad, India, 12‐14 June, 2010.
Henry, N, Fekete, J‐D, McGuffin, MJ. Nodetrix: a hybrid visualization of social networks. IEEE Trans Vis Comput Graph 2007, 13:1302–1309.
Gansner, ER, Hu, Y, Kobourov, S. Visualizing Graphs and Clusters as Maps. IEEE Trans Vis Comput Graph 2010, 30:54–66.
Moscovich, T, Chevalier, F, Henry, N, Pietriga, E, Fekete, J. Topology‐aware navigation in large networks. In: Proceedings of the 27th International Conference on Human factors in Computing Systems (CHI`09), Boston, MA, 4–9 April, 2009. New York, NY: ACM; 2319–2328.

Access to this WIREs title is by subscription only.

Recommend to Your
Librarian Now!

The latest WIREs articles in your inbox

Sign Up for Article Alerts