Re: [igraph] Compare clusterings

[Stijn van Dongen]

   Hi,

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)

<snip>

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.

best,
Stijn

-- 
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