Could affinity propagation be used to obtain a hierarchical clustering of the data?
There are two ways we can think of for doing this. The first is to trace the messages over time and extract a hierarchy of graphs. The second is to run affinity propagation using a low preference (so that few clusters are found), and then successively increase the preference while re-running affinity propagation. This will lead to a sequence of clustering solutions. Interestingly, the resulting sequence of partitions will not form a tree, ie, finer-resolution clusters may overlap the boundaries of courser-resolution clusters. In fact, this is often a desirable property of hierarchical clustering, which standard methods such as agglomerative clustering don’t have. Most of the time, I found that affinity propagation achieves net similarities that are substantially higher than those I could obtain using any other method. But once I saw it find a lower net similarity. Why? Affinity propagation is an approximate method for maximizing the net similarity, a problem that is NP-hard in general.
There are two ways we can think of for doing this. The first is to trace the messages over time and extract a hierarchy of graphs. The second is to run affinity propagation using a low preference (so that few clusters are found), and then successively increase the preference while re-running affinity propagation. This will lead to a sequence of clustering solutions. Interestingly, the resulting sequence of partitions will not form a tree, ie, finer-resolution clusters may overlap the boundaries of courser-resolution clusters. In fact, this is often a desirable property of hierarchical clustering, which standard methods such as agglomerative clustering don’t have. Most of the time, I found that affinity propagation achieves net similarities that are substantially higher than those I could obtain using any other method. But once I saw it find a lower net similarity. Why? Affinity propagation is an approximate method for maximizing the net similarity, a problem that is NP-hard in general.
