Graph Drawing by Classical Multidimensional Scaling: New Perspectives

Klimenta, Mirza and Brandes, Ulrik (2013) Graph Drawing by Classical Multidimensional Scaling: New Perspectives. In: 20th International Symposium, GD 2012, September 19-21, 2012, Redmond, WA, USA , pp. 55-66 (Official URL: http://link.springer.com/chapter/10.1007/978-3-642-36763-2_6).

Full text not available from this repository.

Abstract

With shortest-path distances as input, classical multidimensional scaling can be regarded as a spectral graph drawing algorithm, and recent approximation techniques make it scale to very large graphs. In comparison with other methods, however, it is considered inflexible and prone to degenerate layouts for some classes of graphs. We want to challenge this belief by demonstrating that the method can be flexibly adapted to provide focus+context layouts. Moreover, we propose an alternative instantiation that appears to be more suitable for graph drawing and prevents certain degeneracies.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-36763-2_6
Classifications:M Methods > M.100 Algebraic
P Styles > P.720 Straight-line
ID Code:1297

Repository Staff Only: item control page

References

Bavaud, F.: On the Schoenberg transformations in data analysis: Theory and illustrations. Journal of Classification 28(3), 297–314 (2011)

Borg, I., Groenen, P.: Modern Multidimensional Scaling: Theory and Applications. Springer (2005)

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)

Brandes, U., Pich, C.: An Experimental Study on Distance-Based Graph Drawing. In: Tollis, I.G., Patrignani, M. (eds.) GD 2008. LNCS, vol. 5417, pp. 218–229. Springer, Heidelberg (2009)

Buja, A., Swayne, D.F., Littmann, M.L., Dean, N., Hofmann, H.: Xgvis: Interactive data visualization with mds. Journal of Computational and Graphical Statistics (2001)

Card, S.K., Mackinlay, J.D., Shneiderman, B. (eds.): Readings in Info. Vis.: Using Vision to Think. Morgan Kaufman Publishers (1999)

Civril, A., Magdon-Ismail, M., Bocek-Rivele, E.: SDE: Graph Drawing Using Spectral Distance Embedding. In: Healy, P., Nikolov, N.S. (eds.) GD 2005. LNCS, vol. 3843, pp. 512–513. Springer, Heidelberg (2006)

Çivril, A., Magdon-Ismail, M., Bocek-Rivele, E.: SSDE: Fast Graph Drawing Using Sampled Spectral Distance Embedding. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol. 4372, pp. 30–41. Springer, Heidelberg (2007)

Cox, T., Cox, M.: Multidimensional Scaling. CRC/Chapman and Hall (2001)

France, S.L., Carroll, J.D.: Two-way multidimensional scaling: A review. IEEE Trans. Sys., Man, and Cyber., Part C: Apps. and Reviews 41(5), 644–661 (2011)

Furnas, G.W.: Generalized fisheye views. In: Proc. ACM SIGCHI Conf. Human Factors in Comp. Sys., pp. 16–23. ACM Press (1986)

Gajer, P., Goodrich, M.T., Kobourov, S.G.: A Multi-dimensional Approach to Force-Directed Layouts of Large Graphs. In: Marks, J. (ed.) GD 2000. LNCS, vol. 1984, pp. 211–221. Springer, Heidelberg (2001)

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

Gansner, E.R., Koren, Y., North, S.: Graph Drawing by Stress Majorization. In: Pach, J. (ed.) GD 2004. LNCS, vol. 3383, pp. 239–250. Springer, Heidelberg (2005)

Gower, J.C.: Some distance properties of latent root and vector methods used in multivariate analysis. Biometrika 53, 325–338 (1966)

Gower, J.C.: Euclidean distance geometry. Math. Scientist. 7, 1–14 (1982)

Gower, J.C.: Properties of Euclidean and non-Euclidean distance matrices. Linear Algebra and Its Applications 67, 81–97 (1985)

Hall, K.M.: An r-dimensional quadratic placement algorithm. Management Science 17, 219–229 (1970)

Harel, D., Koren, Y.: Graph Drawing by High-Dimensional Embedding. In: Goodrich, M.T., Kobourov, S.G. (eds.) GD 2002. LNCS, vol. 2528, pp. 207–219. Springer, Heidelberg (2002)

Hosobe, H.: A high-dimensional approach to interactive graph visualization. In: Proc. of ACM Symp. on Applied Comp., pp. 1253–1257. ACM (2004)

Hosobe, H.: An extended high-dimensional method for interactive graph drawing. In: Proc. of the Asia-Pac. Info. Vis., pp. 15–20. Austral. Comp. Soc. (2005)

Kaugars, K., Reinfelds, J., Brazma, A.: A Simple Algorithm for Drawing Large Graphs on Small Screens. In: Tamassia, R., Tollis, I.G. (eds.) GD 1994. LNCS, vol. 894, pp. 278–281. Springer, Heidelberg (1995)

Keahey, T.A., Robertson, E.L.: Techniques for non-linear magnification transformations. In: Proc. IEEE Symp. Info. Vis., pp. 38–46. IEEE Comp. Soc. (1996)

Koren, Y., Carmel, L.: Visualization of labeled data using linear transformations. In: Proc. IEEE Symp. Info. Vis., pp. 121–128. IEEE Comp. Soc. (2003)

Koren, Y., Carmel, L.: Robust linear dimensionality reduction. IEEE Trans. Vis. and Compr. Graph. 10(4), 459–470 (2004)

Kruskal, J.B., Seery, J.B.: Designing network diagrams. In: Proc. of the 1st Gen. Conf. on Soc. Graph., pp. 22–50 (1980)

Misue, K., Sugiyama, K.: Multi-viewpoint perspective display methods: Formulation and application to compound graphs. In: Proc. Conf. on HCI, pp. 834–838. Elsevier (1991)

Sarkar, M., Brown, M.H.: Graphical fisheye views of graphs. In: Proc. Conf. on HCI, pp. 83–91. ACM (1992)

de Silva, V., Tenenbaum, J.B.: Global versus local methods in nonlinear dimensionality reduction. In: Adv. Neur. Info. Process. Sys., vol. 15, pp. 705–712. MIT Press (2003)

Storey, M.D., David Fracchia, F., Mueller, H.A.: Customizing a fisheye view algorithm to preserve the mental map. Jour. Vis. Lang. Comp. 10(3), 245–267 (1999)

Torgerson, W.S.: Multidimensional scaling: I. Theory and method. Psychometrika 17(4), 401–419 (1952)

Tzeng, J., Lu, H.H.S., Li, W.H.: Multidimensional scaling for large genomic datasets. BMC Bioinformatics 9(1), 179–197 (2008)

Webb, A.R.: Statistical Pattern Recognition. John Wiley & Sons (2002)