How many data points can affinity propagation handle on a modern, single-core computer?
For exact affinity propagation, the number of scalar computations is equal to a constant times the number of input similarities, where in practice the constant is approximately 1000. The number of real numbers that need to be stored is equal to 8 times the number of input similarities. So, the number of data points is usually limited by memory. On our 16GB 2.4GHz machine, exact affinity propagation was able to cluster 23,000 data points based on all pairwise similarities (23000×23000) in a few hours. When the number of input similarities is too large, leveraged affinity propagation can be used, which exchanges messages between randomly selected points in each iteration – see here for software. On the same machine, leveraged affinity propagation was able to cluster 120,000 data points in under 1 day.
