Questions concerning the Affinity Propagation Clustering Algorithm

[Jodi]

Hi,

I have a few questions about the Affinity Propagation clustering
algorithm in the clusterMaker plugin. If this is not the appropriate
place to discuss this question can you please direct me?

Question 1:
I find that there is always one cluster identified by the algorithm
that seems to contain completely unrelated (even disconnected) nodes.
I admittedly do not fully understand how Affinity Propagation works,
but is it normal for a cluster to contain nodes that do not have any
connections to each other in the source network (not even via other
nodes)? The other clusters seem reasonable, consisting of only
connected components.

I’m happy to provide examples, but I found this when running with a
variety of different settings, and was thinking that perhaps somebody
here knows the answer at a general level.

Question 2:
I would like to verify the correct input for the Affinity Propagation
clustering algorithm. Is it appropriate to use edge weights from a co-
occurrence (adjacency) matrix? a cosine similarity matrix of the
adjacency matrix?

Question 3:
I would like to run the Affinity Propagation on a very simple network
to gain insight into the algorithm. I created a network with three
disconnected clusters where each cluster has one "hub" node and 8
nodes connected to the "hub" node but not to each other. I obtain an
error with no clusters identified?

Thanks for your help.

[Alexander Pico]

Hi Jodi,

This is the right place to ask these questions, sorry for the delayed
response.

If you could send us example files that would indeed help. I'm also cc'ing
the author of the clusterMaker plugin.

- Alex

[Scooter Morris]

Hi Jodi,
Sorry to take so long to get back to you -- I've been doing a lot
of traveling, which has made it hard for me to keep up with my e-mail :-(

On 04/26/2012 07:34 AM, Jodi wrote:
> Hi,
>
> I have a few questions about the Affinity Propagation clustering
> algorithm in the clusterMaker plugin. If this is not the appropriate
> place to discuss this question can you please direct me?
>
> Question 1:
> I find that there is always one cluster identified by the algorithm
> that seems to contain completely unrelated (even disconnected) nodes.
> I admittedly do not fully understand how Affinity Propagation works,
> but is it normal for a cluster to contain nodes that do not have any
> connections to each other in the source network (not even via other
> nodes)? The other clusters seem reasonable, consisting of only
> connected components.

At any rate, AP should certainly never lump disconnected nodes
together. Can you send me a sample file so I can debug it?
Separately, I've had pretty good success with MCL for partitioning
networks, so you may want to give that a try. I've parallelized it, so
it's also much faster than AP, now.
>
> I�m happy to provide examples, but I found this when running with a

> variety of different settings, and was thinking that perhaps somebody
> here knows the answer at a general level.
>
> Question 2:
> I would like to verify the correct input for the Affinity Propagation
> clustering algorithm. Is it appropriate to use edge weights from a co-
> occurrence (adjacency) matrix? a cosine similarity matrix of the
> adjacency matrix?

The AP algorithm doesn't really care what weights you use. Just make
sure to set the proper weight conversion to make the weights appear as
distances.

>
> Question 3:
> I would like to run the Affinity Propagation on a very simple network
> to gain insight into the algorithm. I created a network with three
> disconnected clusters where each cluster has one "hub" node and 8
> nodes connected to the "hub" node but not to each other. I obtain an
> error with no clusters identified?

Again, if you could send your example, I'll walk through the algorithm.
It may be that the three disconnected hubs represent a case where AP fails.

-- scooter

>
> Thanks for your help.
>
>
>