nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

A Sparse Stress Model

verfasst von : Mark Ortmann, Mirza Klimenta, Ulrik Brandes

Erschienen in: Graph Drawing and Network Visualization

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

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

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

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

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

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

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

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

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel A Distributed Multilevel Force-Directed Algorithm

Nächstes Kapitel Node Overlap Removal by Growing a Tree

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

Titel: A Sparse Stress Model
verfasst von: Mark Ortmann
Mirza Klimenta
Ulrik Brandes
Verlag: Springer International Publishing
Buch: Graph Drawing and Network Visualization
Print ISBN: 978-3-319-50105-5

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

Copyright-Jahr: 2016
DOI: https://doi.org/10.1007/978-3-319-50106-2_2

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"