Abstract
The paper presents self-organizing graphs, a novel approach to graph layout based on a competitive learning algorithm. This method is an extension of self-organization strategies known from unsupervised neural networks, namely from Kohonen’s self-organizing map. Its main advantage is that it is very flexibly adaptable to arbitrary types of visualization spaces, for it is explicitly parameterized by a metric model of the layout space. Yet the method consumes comparatively little computational resources and does not need any heavy-duty preprocessing. Unlike with other stochastic layout algorithms, not even the costly repeated evaluation of an objective function is required. To our knowledge this is the first connectionist approach to graph layout. The paper presents applications to 2D-layout as well as to 3D-layout and to layout in arbitrary metric spaces, such as networks on spherical surfaces.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
J.A. Anderson and E. Rosenfeld, editors. Neurocomputing. MIT Press, Combridge /MA, 1988.
F.J. Brandenburg, editor. Graph Drawing GD’95. Springer, Passau, Germany, September 1995.
F.J. Brandenburg, M. Himsolt, and C. Rohrer. An experimental comparison of force-directed and randomized graph drawing algorithms. In [2], pages 76–87.
I.F. Cruz and J.P. Twarog. 3D graph drawing with simulated annealing. In [2], pages 162–165.
R. Davidson and D. Harel.Drawing graphs nicely using simulated annealing. ACM Transactions on Graphics, 15(4):301–331, October 1996.
G. DiBattista, P. Eades, R. Tamassia, and G. Tollis. Algorithms for drawing graphs: an annotated bibliography. Journal of Computational Geometry Theory and Applications, 4:235–282, 1994.
M. Dorigo, V. Maniezzo, and A. Colorni. The ant system: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, 26(1):29–41, 1996.
P. Eades. A heuristic for graph drawing. Congressus Numerantium, 42:149–160, 1984.
P. Frasconi, M. Gori, and A. Sperduti. A general framework for adaptive processing of data structures. Technical Report 15/97, Universita di Firenze, Florence, 1997.
B. Fritzke. Some competitive learning methods. Unpublished manuscript. http://www.neuroinformatik.ruhr-uni-bochum.de/ini/VDM/research/gsn/JavaPaper/, April 1997.
C. Goller and A. Küchler. Learning task-dependent distributed representations by backpropagation through structure. In International Conference on Neural Networks (ICNN-96), 1996.
G.J. Goodhill and T.J. Sejnowski. A unifying objective function for topographic mappings. Neural Computation, 9:1291–1303, 1997.
S. Grossberg. Adaptive pattern classification and universal recoding: Parallel development and coding of neural feature detectors. Biological Cybernetics, 23:121–134, 1976.
S. Grossberg. How does the brain build a cognitive code? Psychological Review, 87:1–51, 1980.
S. Grossberg. Competitive learning: from interactive activation to adaptive resonance. Cognitive Science, 11:23–63, 1987.
J. Hertz, A. Krogh, and R.G. Palmer. Introduction to the Theory of Neural Computation. Addison-Wesley, Redwood City/CA, 1991.
D. Hubel and T. Wiesel. Receptive fields, binocular interaction and functional architecture in the cat’s visual cortex. Journal of Physiology, 160:173–181, 1962.
T. Kohonen. Self-organized formation of topologically correct feature maps. Biological Cybernetics, 43:59–69, 1982.
T. Kohonen. Self-Organization and Associative Memory. Springer, New York, 1989.
T. Kohonen.Self-Organizing Maps. Springer, New York, 1997.
C. Kosak, J. Marks, and S. Shieber. Automating the layout of network diagrams with specified visual organization. IEEE Transactions on Systems, Man, and Cybernetics, 24(2):440–454, 1994.
S.P. Luttrell. A bayesian analysis of self-organizing maps. Neural Computation, 6:767–794, 1994.
B.D. Ripley. Pattern Recognition and Neural Networks. Cambridge University Press, Cambridge/MA, 1996.
K. Sugiyama. A cognitive approach for graph drawing. Cybernetics and Systems: An International Journal, 18:447–488, 1987.
R. Tamassia. Constraints in graph drawing algorithms. Constraints, An International Journal, 3:87–120, 1998.
C. von der Malsburg. Self-organization of orientation sensitive cells in the striate cortex. Kybernetik, 14:85–100, 1973.
S. Wolfram. The Mathematica Book, Third Edition. Cambridge University Press, Cambridge/MA, 1996.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Meyer, B. (1998). Self-Organizing Graphs — A Neural Network Perspective of Graph Layout. In: Whitesides, S.H. (eds) Graph Drawing. GD 1998. Lecture Notes in Computer Science, vol 1547. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-37623-2_19
Download citation
DOI: https://doi.org/10.1007/3-540-37623-2_19
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-65473-5
Online ISBN: 978-3-540-37623-1
eBook Packages: Springer Book Archive