Energy-Based Clustering of Graphs with Nonuniform Degrees

Andreas Noack
Institute of Computer Science
Brandenburg University of Technology at Cottbus
PO Box 10 13 44, 03013 Cottbus, Germany
an@informatik.tu-cottbus.de

Widely varying node degrees occur in software dependency graphs,
hyperlink structures, social networks, and many other real-world graphs. Finding
dense subgraphs in such graphs is of great practical interest, as these clusters may
correspond to cohesive software modules, semantically related documents, and
groups of friends or collaborators. Many existing clustering criteria and energy
models are biased towards clustering together nodes with high degrees. In this
paper, we introduce a clustering criterion based on normalizing cuts with edge
numbers (instead of node numbers), and a corresponding energy model based on
edge repulsion (instead of node repulsion) that reveal clusters without this bias.