nach oben

Erschienen in:

2015 | OriginalPaper | Buchkapitel

Drawing Large Graphs by Multilevel Maxent-Stress Optimization

verfasst von : Henning Meyerhenke, Martin Nöllenburg, Christian Schulz

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

Drawing large graphs appropriately is an important step for the visual analysis of data from real-world networks. Here we present a novel multilevel algorithm to compute a graph layout with respect to a recently proposed metric that combines layout stress and entropy. As opposed to previous work, we do not solve the linear systems of the maxent-stress metric with a typical numerical solver. Instead we use a simple local iterative scheme within a multilevel approach. To accelerate local optimization, we approximate long-range forces and use shared-memory parallelism. Our experiments validate the high potential of our approach, which is particularly appealing for dynamic graphs. In comparison to the previously best maxent-stress optimizer, which is sequential, our parallel implementation is on average 30 times faster already for static graphs (and still faster if executed on one thread) while producing a comparable solution quality.

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 An Incremental Layout Method for Visualizing Online Dynamic Graphs

Nächstes Kapitel A Million Edge Drawing for a Fistful of Dollars

In fact, Gansner et al. define a slightly more general model that considers the stress term for arbitrary supersets \(S \supseteq E\) and allows variations of the entropy term. Our algorithm also works for the general model; to simplify the description, we restrict ourselves to the default model.

We released the implementation of our algorithms as open source in the KaDraw (Karlsruhe Graph Drawing) framework available at http://algo2.iti.kit.edu/kadraw/.

Abello, J., van Ham, F., Krishnan, N.: ASK-GraphView: a large scale graph visualization system. IEEE Trans. Vis. Comput. Graph. 12(5), 669–676 (2006)CrossRef

Bader, D.A., Meyerhenke, H., Sanders, P., Schulz, C., Kappes, A., Wagner, D.: A benchmark set for graph clustering and graph partitioning. In: Encyclopedia of Social Network Analysis and Mining (2014)

Barnes, J., Hut, P.: A hierarchical \(O(n \log n)\) force-calculation algorithm. Nature 324, 446–449 (1986)CrossRef

Bartel, G., Gutwenger, C., Klein, K., Mutzel, P.: An experimental evaluation of multilevel layout methods. In: Brandes, U., Cornelsen, S. (eds.) GD 2010. LNCS, vol. 6502, pp. 80–91. Springer, Heidelberg (2011) 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) CrossRef

Davis, T.: The university of florida sparse matrix collection (2008). http://www.cise.ufl.edu/research/sparse/matrices

Demetrescu, C., Goldberg, A.V., Johnson, D.S.: The Shortest Path Problem: 9th DIMACS Implementation Challenge, vol. 74. AMS (2009)

Eades, P.: A heuristic for graph drawing. Congressus Numerantium 42, 146–160 (1984)MathSciNet

Frishman, Y., Tal, A.: Multi-level graph layout on the GPU. IEEE Trans. Vis. Comput. Graph. 13(6), 1310–1319 (2007)CrossRef

10.

Fruchterman, T.M.J., Reingold, E.M.: Graph drawing by force-directed placement. Softw. Pract. Exp. 21(11), 1129–1164 (1991)CrossRef

11.

Gajer, P., Kobourov, S.G.: GRIP: Graph drawing with intelligent placement. J. Graph Algorithms Appl. 6(3), 202–224 (2002)MathSciNetCrossRef

12.

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

13.

Gansner, E.R., Koren, Y., North, S.C.: Graph drawing by stress majorization. In: Pach, J. (ed.) GD 2004. LNCS, vol. 3383, pp. 239–250. Springer, Heidelberg (2005) CrossRef

14.

Godiyal, A., Hoberock, J., Garland, M., Hart, J.C.: Rapid multipole graph drawing on the GPU. In: Tollis, I.G., Patrignani, M. (eds.) GD 2008. LNCS, vol. 5417, pp. 90–101. Springer, Heidelberg (2009) CrossRef

15.

Hachul, S., Jünger, M.: Large-graph layout algorithms at work: an experimental study. J. Graph Algorithms Appl. 11(2), 345–369 (2007)MATHMathSciNetCrossRef

16.

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) CrossRef

17.

Holtgrewe, M., Sanders, P., Schulz, C.: Engineering a scalable high quality graph partitioner. In: IEEE Parallel and Distributed Computing (IPDPS 2010), pp. 1–12. IEEE (2010)

18.

Hoske, D., Lukarski, D., Meyerhenke, H., Wegner, M.: Is nearly-linear the same in theory and practice? a case study with a combinatorial laplacian solver. In: Bampis, E. (ed.) SEA 2015. LNCS, vol. 9125, pp. 205–218. Springer, Heidelberg (2015) CrossRef

19.

Hu, Y., Shi, L.: Visualizing large graphs. Wiley Interdisc. Rev. Comput. Stat. 7(2), 115–136 (2015)MathSciNetCrossRef

20.

Ingram, S., Munzner, T., Olano, M.: Glimmer: multilevel MDS on the GPU. IEEE Trans. Vis. Comput. Graph. 15(2), 249–261 (2009)CrossRef

21.

Kamada, T., Kawai, S.: An algorithm for drawing general undirected graphs. Inf. Process. Lett. 31, 7–15 (1989)MATHMathSciNetCrossRef

22.

Kirmani, S., Raghavan, P.: Scalable parallel graph partitioning. In: High Performance Computing, Networking, Storage and Analysis (S 2013), pp. 51:1–51:10. ACM (2013)

23.

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

24.

Koutis, I., Miller, G.L., Tolliver, D.: Combinatorial preconditioners and multilevel solvers for problems in computer vision and image processing. Comput. Vis. Image Underst. 115(12), 1638–1646 (2011)CrossRef

25.

Kruskal, J.B.: Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis. Psychometrika 29(1), 1–27 (1964)MATHMathSciNetCrossRef

26.

Livne, O.E., Brandt, A.: Lean algebraic multigrid (LAMG): fast graph Laplacian linear solver. SIAM J. Sci. Comput. 34(4), B499–B522 (2012)MATHMathSciNetCrossRef

27.

Meyerhenke, H., Nöllenburg, M., Schulz, C.: Drawing large graphs by multilevel maxent-stress optimization. CoRR, arXiv:1506.04383 (2015)

28.

Meyerhenke, H., Sanders, P., Schulz, C.: Partitioning complex networks via size-constrained clustering. In: Gudmundsson, J., Katajainen, J. (eds.) SEA 2014. LNCS, vol. 8504, pp. 351–363. Springer, Heidelberg (2014)

29.

Quigley, A., Eades, P.: FADE: graph drawing, clustering, and visual abstraction. In: Marks, J. (ed.) GD 2000. LNCS, vol. 1984, pp. 197–210. Springer, Heidelberg (2001) CrossRef

30.

Raghavan, U.N., Albert, R., Kumara, S.: Near linear time algorithm to detect community structures in large-scale networks. Phy. Rev. E 76(3), 036106 (2007)CrossRef

31.

Soper, A.J., Walshaw, C., Cross, M.: A combined evolutionary search and multilevel optimisation approach to graph-partitioning. J. Global Optim. 29(2), 225–241 (2004)MATHMathSciNetCrossRef

32.

Walshaw, C.: A multilevel algorithm for force-directed graph-drawing. J. Graph Algorithms Appl. 7(3), 253–285 (2003)MATHMathSciNetCrossRef

Titel: Drawing Large Graphs by Multilevel Maxent-Stress Optimization
verfasst von: Henning Meyerhenke
Martin Nöllenburg
Christian Schulz
Verlag: Springer International Publishing
Buch: Graph Drawing and Network Visualization
Print ISBN: 978-3-319-27260-3

Electronic ISBN: 978-3-319-27261-0

Copyright-Jahr: 2015
DOI: https://doi.org/10.1007/978-3-319-27261-0_3

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"