Top

previous chapter A Distributed Multilevel Force-Directed Algorithm

next chapter Node Overlap Removal by Growing a Tree

Hint

Swipe to navigate through the chapters of this book

2016 | OriginalPaper | Chapter

A Sparse Stress Model

Read first chapter

Authors: Mark Ortmann, Mirza Klimenta, Ulrik Brandes

Publisher: Springer International Publishing

Published in: Graph Drawing and Network Visualization

» Get access to the full-text

Abstract

Force-directed layout methods constitute the most common approach to draw general graphs. Among them, stress minimization produces layouts of comparatively high quality but also imposes comparatively high computational demands. We propose a speed-up method based on the aggregation of terms in the objective function. It is akin to aggregate repulsion from far-away nodes during spring embedding but transfers the idea from the layout space into a preprocessing phase. An initial experimental study informs a method to select representatives, and subsequent more extensive experiments indicate that our method yields better approximations of minimum-stress layouts in less time than related methods.

Please log in to get access to this content

To get access to this content you need the following product:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 69.000 Bücher
über 500 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Umwelt
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 50.000 Bücher
über 380 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Umwelt
Maschinenbau + Werkstoffe

Testen Sie jetzt 30 Tage kostenlos.

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 58.000 Bücher
über 300 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

inform now

https://github.com/marckhoury/mars.

We are grateful to Yifan Hu for providing us with the code.

http://www.cs.arizona.edu/~kobourov/GRIP/.

Barnes, J., Hut, P.: A hierarchical O( \(n \log n\)) force-calculation algorithm. Nature 324(6096), 446–449 (1986). http://dx.doi.org/10.1038/324446a0 CrossRef

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

Brandes, U.: Drawing on physical analogies. In: Kaufmann, M., Wagner, D. (eds.) Drawing Graphs. LNCS, vol. 2025, pp. 71–86. Springer, Heidelberg (2001). doi: 10.1007/3-540-44969-8_4 CrossRef

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). doi: 10.1007/978-3-540-70904-6_6 CrossRef

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). doi: 10.1007/978-3-642-00219-9_21 CrossRef

Brandes, U., Schulz, F., Wagner, D., Willhalm, T.: Travel planning with self-made maps. In: Buchsbaum, A.L., Snoeyink, J. (eds.) ALENEX 2001. LNCS, vol. 2153, pp. 132–144. Springer, Heidelberg (2001). doi: 10.1007/3-540-44808-X_10 CrossRef

Cohen, J.D.: Drawing graphs to convey proximity: an incremental arrangement method. ACM Trans. Comput. Hum. Interact. 4(3), 197–229 (1997). http://doi.acm.org/10.1145/264645.264657 CrossRef

Davis, T.A., Hu, Y.: The university of Florida sparse matrix collection. ACM Trans. Math. Softw. 38(1), 1: 1–1: 25 (2011). http://www.cise.ufl.edu/research/sparse/matrices MathSciNet

Drineas, P., Frieze, A.M., Kannan, R., Vempala, S., Vinay, V.: Clustering large graphs via the singular value decomposition. Mach. Learn. 56(1–3), 9–33 (2004). http://dx.doi.org/10.1023/B:MACH.0000033113.59016.96 CrossRefMATH

10.

Frick, A., Ludwig, A., Mehldau, H.: A fast adaptive layout algorithm for undirected graphs (extended abstract and system demonstration). In: Tamassia, R., Tollis, I.G. (eds.) GD 1994. LNCS, vol. 894, pp. 388–403. Springer, Heidelberg (1995). doi: 10.1007/3-540-58950-3_393 CrossRef

11.

Fruchterman, T.M.J., Reingold, E.M.: Graph drawing by force-directed placement. Softw. Pract. Exp. 21(11), 1129–1164 (1991). http://dx.doi.org/10.1002/spe.4380211102 CrossRef

12.

Gabriel, R.K., Sokal, R.R.: A new statistical approach to geographic variation analysis. Syst. Zool. 18(3), 259–278 (1969) CrossRef

13.

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). doi: 10.1007/3-540-44541-2_20 CrossRef

14.

Gansner, E.R., Hu, Y., Krishnan, S.: COAST: a convex optimization approach to stress-based embedding. In: Wismath, S., Wolff, A. (eds.) GD 2013. LNCS, vol. 8242, pp. 268–279. Springer, Heidelberg (2013). doi: 10.1007/978-3-319-03841-4_24 CrossRef

15.

Gansner, E.R., Hu, Y., North, S.C.: A maxent-stress model for graph layout. IEEE Trans. Vis. Comput. Graph. 19(6), 927–940 (2013) CrossRef

16.

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). doi: 10.1007/978-3-540-31843-9_25 CrossRef

17.

Greengard, L.: The Rapid evaluation of potential fields in particle systems. ACM distinguished dissertations, MIT Press, Cambridge (1988). http://opac.inria.fr/record=b1086802

18.

Hachul, S., Jünger, M.: Drawing large graphs with a potential-field-based multilevel algorithm. In: Pach, J. (ed.) GD 2004. LNCS, vol. 3383, pp. 285–295. Springer, Heidelberg (2005). doi: 10.1007/978-3-540-31843-9_29 CrossRef

19.

Hall, K.M.: An \(r\)-dimensional quadratic placement algorithm. Manag. Sci. 17(3), 219–229 (1970). http://dx.doi.org/10.1287/mnsc.17.3.219 CrossRefMATH

20.

Hu, Y., Shi, L.: Visualizing large graphs. Wiley Interdiscip. Rev. Comput. Stat. 7(2), 115–136 (2015). http://dx.doi.org/10.1002/wics.1343 MathSciNetCrossRef

21.

Hu, Y.F.: Efficient and high quality force-directed graph drawing. Mathematica J. 10, 37–71 (2005). http://www.mathematica-journal.com/issue/v10i1/contents/graph_draw/graph_draw.pdf

22.

Ingram, S., Munzner, T.: Glint: An MDS framework for costly distance functions. In: Kerren, A., Seipel, S. (eds.) Proceedings of SIGRAD 2012, Interactive Visual Analysis of Data. Linköping Electronic Conference Proceedings, vol. 81, pp. 29–38. Linköping University Electronic Press (2012). http://www.ep.liu.se/ecp_article/index.en.aspx?issue=081;article=005

23.

Khoury, M., Hu, Y., Krishnan, S., Scheidegger, C.E.: Drawing large graphs by low-rank stress majorization. Comput. Graph. Forum 31(3), 975–984 (2012). http://dx.doi.org/10.1111/j.1467-8659.2012.03090.x CrossRef

24.

Klimenta, M., Brandes, U.: Graph drawing by classical multidimensional scaling: new perspectives. In: Didimo, W., Patrignani, M. (eds.) GD 2012. LNCS, vol. 704, pp. 55–66. Springer, Heidelberg (2013). doi: 10.1007/978-3-642-36763-2_6

25.

Kobourov, S.G.: Force-directed drawing algorithms. In: Tamassia, R. (ed.) Handbook of Graph Drawing and Visualization, pp. 383–408. CRC Press, Boca Raton (2013)

26.

Koren, Y., Carmel, L., Harel, D.: ACE: A fast multiscale eigenvectors computation for drawing huge graphs. In: Wong, P.C., Andrews, K. (eds.) InfoVis 2002, pp. 137–144. IEEE Computer Society (2002). http://dx.doi.org/10.1109/INFVIS.2002.1173159

27.

McGee, V.E.: The multidimensional analysis of “elastic” distances. Br. J. Math. Stat. Psychol. 19(2), 181–196 (1966). http://dx.doi.org/10.1111/j.2044-8317.1966.tb00367.x CrossRef

28.

Meyerhenke, H., Nöllenburg, M., Schulz, C.: Drawing large graphs by multilevel maxent-stress optimization. In: Di Giacomo, E., Lubiw, A. (eds.) GD 2015. LNCS, vol. 9411, pp. 30–43. Springer, Heidelberg (2015). doi: 10.1007/978-3-319-27261-0_3 CrossRef

29.

Ortmann, M., Klimenta, M., Brandes, U.: A sparse stress model. CoRR abs/1608.08909 (2016). http://arxiv.org/abs/1608.08909

30.

Quigley, A.J.: Large scale relational information visualization, clustering, and abstraction. Ph.D. thesis, University of Newcastle (2000)

31.

Sibson, R.: Studies in the robustness of multidimensional scaling: procrustes statistics. J. Roy. Stat. Soc. Ser. B (Methodol.) 40(2), 234–238 (1978). http://www.jstor.org/stable/2984761 MathSciNetMATH

32.

de Silva, V., Tenenbaum, J.B.: Global versus local methods in nonlinear dimensionality reduction. In: Becker, S., Thrun, S., Obermayer, K. (eds.) NIPS 2002, pp. 705–712. MIT Press, Cambridge (2002). http://papers.nips.cc/paper/2141-global-versus-local-methods-in-nonlinear-dimensionality-reduction

33.

Tunkelang, D.: JIGGLE: java interactive graph layout environment. In: Whitesides, S.H. (ed.) GD 1998. LNCS, vol. 1547, pp. 413–422. Springer, Heidelberg (1998). doi: 10.1007/3-540-37623-2_33 CrossRef

34.

Tunkelang, D.: A numerical optimization approach to general graph drawing. Ph.D. thesis, Carnegie Mellon University (1999)

35.

Walshaw, C.: A multilevel algorithm for force-directed graph-drawing. J. Graph Algorithms Appl. 7(3), 253–285 (2003). http://www.cs.brown.edu/publications/jgaa/accepted/2003/Walshaw2003.7.3.pdf MathSciNetCrossRefMATH

Title

A Sparse Stress Model

Book

Graph Drawing and Network Visualization

Print ISBN: 978-3-319-50105-5

Electronic ISBN: 978-3-319-50106-2

https://doi.org/10.1007/978-3-319-50106-2

DOI

https://doi.org/10.1007/978-3-319-50106-2_2

Authors:

Mark Ortmann
Mirza Klimenta
Ulrik Brandes

Publisher

Springer International Publishing

Sequence number

Premium Partner

Image Credits