  Soft-constraint affinity propagation (SCAP) is a new statistical-physics
based clustering technique. First we give the derivation of a simplified
version of the algorithm and discuss possibilities of time- and
memory-efficient implementations. Later we give a detailed analysis of the
performance of SCAP on artificial data, showing that the algorithm efficiently
unveils clustered and hierarchical data structures. We generalize the algorithm
to the problem of semi-supervised clustering, where data are already partially
labeled, and clustering assigns labels to previously unlabeled points. SCAP
uses both the geometrical organization of the data and the available labels
assigned to few points in a computationally efficient way, as is shown on
artificial and biological benchmark data.

Data Analysis, Statistics and Probability;Statistical Mechanics;Quantitative Methods