Home | Issues | About JGAA | Instructions for Authors |
Special Issue on Selected Papers from the Thirteenth International Symposium on Graph Drawing, GD 2005
DOI: 10.7155/jgaa.00154
Energy Models for Graph Clustering
Vol. 11, no. 2, pp. 453-480, 2007. Regular paper.
Abstract The cluster structure of many real-world graphs is of great interest,
as the clusters may correspond e.g. to communities in social networks
or to cohesive modules in software systems.
Layouts can naturally represent the cluster structure of graphs
by grouping densely connected nodes and separating sparsely connected nodes.
This article introduces two energy models whose minimum energy layouts
represent the cluster structure, one based on repulsion between nodes
(like most existing energy models) and one based on repulsion between edges.
The latter model is not biased towards grouping nodes with high degrees,
and is thus more appropriate for the many real-world graphs
with right-skewed degree distributions.
The two energy models are shown to be closely related to widely used
quality criteria for graph clusterings - namely the density of the cut,
Shi and Malik's normalized cut, and Newman's modularity - and
to objective functions optimized by eigenvector-based graph drawing methods.
|
Journal Supporters
|