An Energy Model for Visual Graph Clustering

Noack, Andreas (2004) An Energy Model for Visual Graph Clustering. In: Graph Drawing 11th International Symposium, GD 2003, September 21-24, 2003, Perugia, Italy , pp. 425-436 (Official URL: http://dx.doi.org/10.1007/978-3-540-24595-7_40).

Full text not available from this repository.

Abstract

We introduce an energy model whose minimum energy drawings reveal the clusters of the drawn graph. Here a cluster is a set of nodes with many internal edges and few edges to nodes outside the set. The drawings of the best-known force and energy models do not clearly show clusters for graphs whose diameter is small relative to the number of nodes. We formally characterize the minimum energy drawings of our energy model. This characterization shows in what sense the drawings separate clusters, and how the distance of separated clusters to the other nodes can be interpreted.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-24595-7_40
Classifications:P Styles > P.180 Cluster
M Methods > M.400 Force-directed / Energy-based
ID Code:472

Repository Staff Only: item control page

References

R. Albert and A.-L. Barabási. Statistical mechanics of complex networks. Reviews of Modern Physics, 74(1):47-97, 2002.

C. J. Alpert and A. B. Kahng. Recent directions in netliat partitioning: A survey. Integration, the VLSI Journal, 19(1-2):1-81, 1995.

Y. Aumann and Y. Rabani. An 0(log k) approximate min-cut max-flow theorem and approximation algorithm. SIAM Journal on Computing, 27(1):291-301, 1998.

G. D. Battista, P. Eades, R. Tamassia, and I. G. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall, 1999.

J. Blythe, C. McGrath, and D. Krackhardt. The effect of graph layout on inference from social network data. In F.-J. Brandenburg, editor, Proc. Symposium on Graph Drawing (GD 1995), LNCS 1027, pages 40-51, 1996. Springer-Verlag.

F.-J. Brandenburg, M. Himsolt, and C. Rohrer. An experimental comparison of force-directed and randomized graph drawing algorithms. In F.-J. Brandenburg, editor, Proc. Symposium on Graph Drawing (GD 1995), LNCS 1027, pages 76-87, 1996. Springer-Verlag.

U. Brandes. Drawing on physical analogies. In M. Kaufmann and D. Wagner, editors, Drawing Graphs: Methods and Models, LNCS 2025, pages 71-86. Springer-Verlag, 2001.

U. Brandes and S. Cornelsen. Visual ranking of link structures. In F. Dehne, J.-R. Sack, and R. Tamassia, editors, Proc. 7th International Workshop on Algorithms and Data Structures (WADS 2001), LNCS 2125, pages 222-233, 2001. Springer-Verlag.

R. Brockenauer and S. Cornelsen. Drawing clusters and hierarchies. In M. Kaufmann and D. Wagner, editors, Drawing Graphs: Methods and Models, LNCS 2025. Springer-Verlag, 2001.

R. Davidson and D. Harel. Drawing graphs nicely using simulated annealing. ACM Transactions on Graphics, 15(4):301-331, 1996.

E. Dengler and W. Cowan. Human perception of laid-out graphs. In S. H. Whitesides, editor, Proc. 6th International Symposium on Graph Drawing (GD 1998), LNCS 1547, pages 441-443, 1998. Springer-Verlag.

P. Eades. A heuristic for graph drawing. Congressus Numerantium, 42:149-160, 1984.

P. Eades and M. L. Huang. Navigating clustered graphs using force-directed methods. Journal of Graph Algorithms and Applications, 4(3):157-181, 2000.

T. M. J. Fruchterman and E. M. Reingold. Graph drawing by force-directed placement. Software - Practice and Experience, 21(11):1129-1164, 1991.

P. Gajer, M. T. Goodrich, and S. G. Kobourov. A multi-dimensional approach to force-directed layouts of large graphs. In J. Marks, editor, Proc. 8th International Symposium on Graph Drawing (GD2000), LNCS 1984, pages 211-221. Springer-Verlag.

K. M. Hall. An r-dimensional quadratic placement algorithm. Management Science, 17(3):219-229, 1970.

D. Harel and Y. Koren. A fast multi-scale method for drawing large graphs. In J. Marks, editor, Proc. 8th International Symposium on Graph Drawing (GD 2000), LNCS 1984, pages 183-196, 2001. Springer-Verlag.

T. Kamada and S. Kawai. An algorithm for drawing general undirected graphs. Information Processing Letters, 31(1):7-15, 1989.

Y. Koren, L. Carmel, and D. Harel. Ace: A fast multiscale eigenvector computation for drawing huge graphs. In Proc. IEEE Symposium on Information Visualization (InfoVis 2002), pages 137-144, 2002.

J. B. Kruskal and M. Wish. Multidimensional Scaling. Sage Publications, 1978.

C. Lewerentz and A. Noack. CrocoCosmos - 3D visualization of large object-oriented programs. In Graph Drawing Software, pages 279-297. Springer-Verlag, 2003.

N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215-245, 1995.

S. Mancoridis, B. S. Mitchell, C. Rorres, Y. Chen, and E. R. Gansner. Using automatic clustering to produce high-level system organizations of source code. In Proc. 6th IEEE International Workshop on Program Understanding (IWPC 1998), pages 45-52, 1998.

A. Noack. Energy models for drawing clustered small-world graphs. Technical Report 07/03, Institute of Computer Science, Brandenburg University of Technology at Cottbus, 2003.

A. Pothen. Graph partitioning algorithms with applications to scientific computing. In D. E. Keyes, A. Sameh, and V. Venkatakrishnan, editors, Parallel Numerical Algorithms, pages 323-368. Kluwer, 1997.

A.J. Quigley and P. Eades. FADE: Graph drawing, clustering, and visual abstraction. In J. Marks, editor, Proc. 8th International Symposium on Graph Drawing (GD 2000), LNCS 1984, pages 197-210, 2001. Springer-Verlag.

S. H. Strogatz. Exploring complex networks. Nature, 410:268-276, 2001.

Daniel Tunkelang. A Numerical Optimization Approach to General Graph Drawing. PhD thesis, School of Computer Science, Carnegie Mellon University, 1999.

C. Walshaw. A multilevel algorithm for force-directed graph drawing. In J. Marks, editor, Proc. 8th International Symposium on Graph Drawing (GD 2000), LNCS 1984, pages 171-182, 2001. Springer-Verlag.

X. Wang and I. Miyamoto. Generating customized layouts. In F.-J. Brandenburg, editor, Proc. Symposium on Graph Drawing (GD 1995), LNCS 1027, pages 504-515, 1996. Springer-Verlag.