Abstract
Graphs are common data structures in computer science used to capture relations between set of objects. Graph drawing is a visual representation of the graph in more readable form, usually with vertices projected into ℝ2 space. Dimension reduction methods are designed to transform original data in high-dimensional space into a new data in lower-dimensional space. This work is focused on selected dimension reduction methods and their use to obtain sensible graph drawing from the original graph. Results of the dimension reduction methods are discussed and compared to each other and also to the classical approach presented by Kamada and Kawai.
This is a preview of subscription content, log in via an institution.
Buying options
Tax calculation will be finalised at checkout
Purchases are for personal use only
Learn about institutional subscriptionsPreview
Unable to display preview. Download preview PDF.
References
Abdi, H., Williams, L.J.: Principal component analysis. Wiley Interdisciplinary Reviews: Computational Statistics 2(4), 433–459 (2010)
Aldous, D., Fill, J.A.: Reversible markov chains and random walks on graphs (2002), unfinished monograph, recompiled 2014
Arenas, A.: Alex arenas website (2009), http://deim.urv.cat/~aarenas/data/welcome
Chan, T.M.: All-pairs shortest paths for unweighted undirected graphs in o(mn) time. In: Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 514–523 (2006)
Cohen, R.F., Battista, G.D., Tamassia, R., Tollis, I.G.: A framework for dynamic graph drawing. Congressus Numerantium 42, 149–160 (1992)
Coifman, R.R., Lafon, S.: Diffusion maps. Applied and Computational Harmonic Analysis 21(1), 5–30 (2006); Special Issue: Diffusion Maps and Wavelets
Cunningham, P.: Dimension reduction. In: Machine Learning Techniques for Multimedia, pp. 91–112. Springer (2008)
Cureton, E., D’Agostino, R.: Factor Analysis: An Applied Approach. Taylor & Francis (2013)
Díaz, J., Petit, J., Serna, M.: A survey of graph layout problems. ACM Comput. Surv. 34(3), 313–356 (2002)
Diestel, R.: Graph Theory. Electronic library of mathematics. Springer (2006)
Forrester, D., Kobourov, S.G., Navabi, A., Wampler, K., Yee, G.V.: Graphael: A system for generalized force-directed layouts. In: Pach, J. (ed.) GD 2004. LNCS, vol. 3383, pp. 454–464. Springer, Heidelberg (2005)
Fruchterman, T.M.J., Reingold, E.M.: Graph drawing by force-directed placement. Softw. Pract. Exper. 21(11), 1129–1164 (1991)
Gross, J.L., Yellen, J.: Graph Theory and Its Applications, Second Edition (Discrete Mathematics and Its Applications). Chapman & Hall/CRC (2005)
Harman, H.: Modern Factor Analysis. University of Chicago Press (1976)
Herman, I., Society, I.C., Melançon, G., Marshall, M.S.: Graph visualization and navigation in information visualization: a survey. IEEE Transactions on Visualization and Computer Graphics 6, 24–43 (2000)
Hinton, G.E., Roweis, S.T.: Stochastic neighbor embedding. In: NIPS, pp. 833–840 (2002)
Kamada, T., Kawai, S.: An algorithm for drawing general undirected graphs. Information Processing Letters 31(1), 7–15 (1989)
Kaufmann, M., Wagner, D. (eds.): Drawing Graphs. LNCS, vol. 2025. Springer, Heidelberg (2001)
Kobourov, S.G.: Spring embedders and force directed graph drawing algorithms. CoRR abs/1201.3011 (2012)
Koren, Y.: Drawing graphs by eigenvectors: theory and practice. Computers and Mathematics with Applications 49(11-12), 1867–1888 (2005)
Kullback, S., Leibler, R.A.: On information and sufficiency. The Annals of Mathematical Statistics 22(1), 79–86 (1951)
Meyerhenke, H.: 10th dimacs implementation challenge - graph partitioning and graph clustering (2012)
Nadler, B., Lafon, S., Coifman, R.R., Kevrekidis, I.G.: Diffusion maps, spectral clustering and reaction coordinates of dynamical systems. Applied and Computational Harmonic Analysis 21(1), 113–127 (2006); Special Issue: Diffusion Maps and Wavelets
Newmann, M.: Network data (2013), http://www-personal.umich.edu/~mejn/netdata/
Norris, J.: Markov Chains, No. č 2008. Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge Series in (1998)
Plastria, F., De Bruyne, S., Carrizosa, E.: Dimensionality reduction for classification. In: Tang, C., Ling, C.X., Zhou, X., Cercone, N.J., Li, X. (eds.) ADMA 2008. LNCS (LNAI), vol. 5139, pp. 411–418. Springer, Heidelberg (2008)
Seidel, R.: On the all-pairs-shortest-path problem in unweighted undirected graphs. J. Comput. Syst. Sci. 51(3), 400–403 (1995)
Sorzano, C.O.S., Vargas, J., Pascual-Montano, A.D.: A survey of dimensionality reduction techniques. CoRR abs/1403.2877 (2014)
Zaoralek, L., Peterek, T., Dohnálek, P., Gajdos, P.: Comparison of feature reduction methods in the task of arrhythmia classification. In: IBICA, pp. 375–382 (2014)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Buriánek, T., Zaorálek, L., Snášel, V., Peterek, T. (2015). Graph Drawing Using Dimension Reduction Methods. In: Abraham, A., Krömer, P., Snasel, V. (eds) Afro-European Conference for Industrial Advancement. Advances in Intelligent Systems and Computing, vol 334. Springer, Cham. https://doi.org/10.1007/978-3-319-13572-4_17
Download citation
DOI: https://doi.org/10.1007/978-3-319-13572-4_17
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-13571-7
Online ISBN: 978-3-319-13572-4
eBook Packages: EngineeringEngineering (R0)