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.