Energy-Based Clustering of Graphs with Nonuniform Degrees

Noack, Andreas (2006) Energy-Based Clustering of Graphs with Nonuniform Degrees. In: Graph Drawing 13th International Symposium, GD 2005, September 12-14, 2005, Limerick, Ireland , pp. 309-320 (Official URL:

Full text not available from this repository.


In many real-world graphs, like social networks, hyperlink structures, and software dependency graphs, the degrees of the nodes vary widely. Finding clusters (i.e., dense subgraphs) in such graphs is of great practical interest, as these clusters may correspond to groups of friends or collaborators, semantically related documents, and cohesive software modules. Many existing clustering criteria and energy models are biased towards clustering together nodes with high degrees. In this paper, we develop a clustering criterion based on normalized cuts, and an energy model that uses edge repulsion instead of node repulsion to produce drawings that reveal clusters without this bias.

Item Type:Conference Paper
Additional Information:10.1007/11618058_28
Classifications:P Styles > P.180 Cluster
M Methods > M.400 Force-directed / Energy-based
ID Code:700

Repository Staff Only: item control page


Reka Albert and Albert-Laszlo Barabasi.: Statistical mechanics of complex networks. Reviews of Modern Physics, 74(1):47--97, 2002.

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

Josh Barnes and Piet Hut.: A hierarchical O(N log N) force-calculation algorithm. Nature, 324:446--449, 1986.

Jim Blythe, Cathleen McGrath, and David Krackhardt.: The effect of graph layout on inference from social network data. Proc. GD 1995, pages 40--51. Springer-Verlag, 1996.

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

Edmund Dengler and William Cowan.: Human perception of laid-out graphs. Proc. GD 1998, pages 441--443. Springer-Verlag, 1998.

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

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

Pawel Gajer, Michael T. Goodrich, and Stephen G. Kobourov. A multi-dimensional approach to force-directed layouts of large graphs. Proc. GD 2000, pages 211--221. Springer-Verlag, 2001.

Stefan Hachul and Michael Jünger. Drawing large graphs with a potential-field-based multilevel algorithm. Proc. GD 2004, pages 285--295. Springer-Verlag, 2004.

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

David Harel and Yehuda Koren.: A fast multi-scale method for drawing large graphs. Proc. GD 2000, pages 183--196. Springer-Verlag, 2001.

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

Ravi Kannan, Santosh Vempala, and Adrian Vetta.: On clusterings: Good, bad and spectral. Journal of the ACM, 51(3):497--515, 2004.

Tom Leighton and Satish Rao.: An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms. Proc. 29th Annual Symposium on Foundations of Computer Science (FOCS 1988), pages 422--431. IEEE, 1988.

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. Proc. 6th IEEE International Workshop on Program Comprehension (IWPC 1998), pages 45--52. IEEE, 1998.

Andreas Noack.: An energy model for visual graph clustering. Proc. GD 2003, pages 425--436. Springer-Verlag, 2004.

Andreas Noack and Claus Lewerentz.: A space of layout styles for hierarchical graph models of software systems. Proc. 2nd ACM Symposium on Software Visualization (SoftVis 2005), pages 155--164. ACM, 2005.

Aaron J. Quigley and Peter Eades.: FADE: Graph drawing, clustering, and visual abstraction. Proc. GD 2000, pages 197--210. Springer-Verlag, 2001.

Jianbo Shi and Jitendra Malik.: Normalized cuts and image segmentation. IEEE Transaction on Pattern Analysis and Machine Intelligence, 22(8):888--905, 2000.

Chris Walshaw.: A multilevel algorithm for force-directed graph drawing. Proc. GD 2000, pages 171--182. Springer-Verlag, 2001.

Zhenyu Wu and Richard Leahy.: An optimal graph theoretic approach to data clustering: Theory and its application to image segmentation. IEEE Transaction on Pattern Analysis and Machine Intelligence, 15(11):1101--1113, 1993.