title: Dominant sets and pairwise clustering.
abstract: We develop a new graph-theoretic approach for pairwise data clustering which is motivated by the analogies between the intuitive concept of a cluster and that of a dominant set of vertices, a notion introduced here which generalizes that of a maximal complete subgraph to edge-weighted graphs. We establish a correspondence between dominant sets and the extrema of a quadratic form over the standard simplex, thereby allowing the use of straightforward and easily implementable continuous optimization techniques from evolutionary game theory. Numerical examples on various point-set and image segmentation problems confirm the potential of the proposed approach.
authors.affiliation: Dipartimento de Informatica, Università Ca'Foscari de Venezia, Venezia Mestre, Italy. pavan@dsi.unive.it
authors.forename: Massimiliano
authors.initials: M
authors.lastname: Pavan
authors.forename: Marcello
authors.initials: M
authors.lastname: Pelillo
mesh_terms: D000465:Algorithms; D001185:Artificial Intelligence; D016000:Cluster Analysis; D007089:Image Enhancement / Q000379:methods*; D007090:Image Interpretation, Computer-Assisted / Q000379:methods*; D016247:Information Storage and Retrieval / Q000379:methods*; D010363:Pattern Recognition, Automated / Q000379:methods*