[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [igraph] Compare clusterings

From: Stijn van Dongen
Subject: Re: [igraph] Compare clusterings
Date: Fri, 23 Jul 2010 17:34:38 +0100
User-agent: Mutt/


On Fri, Jul 23, 2010 at 05:19:50PM +0100, Tamas Nepusz wrote:
> >   Hello!  I installed igraph as an R package. If i run two clustering
> >   algorithms on the same graph and i have the two membership vector
> >   then, how can i compare the two partitions? I would like to know
> >   which points changed their cluster?  Thank you  Albert
> Well, the problem is not as simple as it seems; consider the following
> two membership vectors:
> c(1,1,1,1,2,1,2,2,2,2)
> c(2,2,2,2,2,1,1,1,1,1)


Tamas is correct of course, and if two clusterings are very different
it will be generally impossible to establish such a simple
transformational pattern of points changing clusters.
A less ambitious but informative and doable approach is to consider the 
contingency table
between the two clusterings  -- simply a table containing the sizes of the
intersections of all possible pairings of clusters.

Two clusters (say c1 and d1) that have a large intersection (say larger than
either of the two set differences) can serve as anchors between the two
clusterings; you could say an abstract set S is represented by c1 in the first
clustering and d1 in the second clustering, and relative to S you could make
statements of transformations such as you suggest. But the number of anchors
you are able to find is not clear in advance. It could be a lot or a few, but
the scenario that not both of your clusterings are fully covered by such
anchors is pretty realistic.

I have not used igraph a lot yet, so I don't know what would be a good way
to create such a contingency table.


Stijn van Dongen         >8<        -o)   O<  forename pronunciation: [Stan]
EMBL-EBI                            /\\   Tel: +44-(0)1223-492675
Hinxton, Cambridge, CB10 1SD, UK   _\_/   http://micans.org/stijn

reply via email to

[Prev in Thread] Current Thread [Next in Thread]