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 , 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

Actions (login required)

View Item View Item