Affinity Propagation

When considering clustering methods for similarity and clustering one should try a newer algorithm called Affinity Propagation. Instead of iterating on a defined set of points, Affinity Propagation works by setting up a factor graph that describes the objective function used to identify exemplars and cluster data. The algorithm then iterates for this objective function across ALL exemplars. Of great importance is AP's algorithm's time and memory requirements scale linearly with the number of similarities, which would be NxN if a full set of pairwise similarities is input, but much, much less if the set of similarities is sparse.