Self-Organizing Graphs - A Neural Network Perspective of Graph Layout

Meyer, Bernd (1998) Self-Organizing Graphs - A Neural Network Perspective of Graph Layout. In: Graph Drawing 6th International Symposium, GD’ 98, August 13-15, 1998, Montréal, Canada , pp. 246-262 (Official URL: http://dx.doi.org/10.1007/3-540-37623-2_19).

Full text not available from this repository.

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.

Item Type:Conference Paper
Additional Information:10.1007/3-540-37623-2_19
Classifications:M Methods > M.300 Dynamic / Incremental / Online
G Algorithms and Complexity > G.999 Others
M Methods > M.900 Tree
P Styles > P.060 3D
ID Code:311

Repository Staff Only: item control page

References

J.A. Anderson and E. Rosenfeld, editors. Neurocomputing. MIT Press, Cambridge/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 simmulated annealing. ACM Transactions on Graphics, 15(4):301-331, 1996.

G. Di Battista, P. Eades, R. Tamassia, and I.G. Tollis. Algorithms for drawing graphs: An annotated bibliography. Comput. Geom. Theory Appl., 4: 235-282, 1994.

M. Dorigo, V. Maniezzo, and A. Colorini. The ant system: Optimization by a colony of coopersting 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. 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 hte 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/CA, 1996.