Clustering by Passing Messages

As recently published in Science (see reference)

Simple and effective means of clustering any data for which a similarity matrix can be constructed. Does not require similarity matrix meet the standards for a metric. The algorithm applies in cases where the similarity matrix is not symmetric (the distance from point i to j can be different from j to i). And it does not require triangular equalities (e.g. the hypoteneus can be less than the sum of the other sides)

usage is very simple (given an m x m similarity matrix)

ex = affprop(s)

returns ex, a m x 1 vector of indices, such that ex(i) is the exemplar for the ith point.

see affyprop_demo for a complete example with simple 2d data. See reference for more complex examples including face matching.