Re: [igraph] dissimilarity-based community detection

[Tamas Nepusz]

Hi Kurt,

> 1 - I am using python and just easy_installed igraph-0.4.5.   
> igraph.Graph.community_walktrap() does not seem to be present - do i  
> need the development version??
igraph-0.4.5 is indeed not the most recent version. The most recent is  
igraph-0.5 which includes community_walktrap. The reason why you  
installed 0.4.5 is that the package has been renamed in the meanwhile  
to python-igraph. Try easy_installing python-igraph instead to get the  
most recent version. Another change was that python-igraph does not  
include the C core of igraph anymore, so it must be downloaded and  
installed separately before compiling python-igraph. However, if you  
use Windows, there's a ready-made installer which just installs  
everything what's needed. If you use Debian Linux, you can just use  
our package repository and install the igraph and python-igraph  
packages. If you use OS X Leopard on an Intel-based Mac, there's a pre- 
compiled meta-package on the igraph homepage.

> I am really only interested in the "back-half" of the algorithm,  
> using the dissimilarity matrix and a threshold value to detect  
> communities...
Well, in this case you have implement it yourself (or convert the  
dissimilarity values to similarities somehow and use  
walktrap_community - but maybe it's worth thresholding the similarity  
values before trying that). If you use numpy to maintain the  
dissimilarity matrix and record your merging steps in a separate  
Python list, you can use that list to construct an  
igraph.VertexDendrogram object by performing the steps "backwards" and  
joining the vertices one by one. This is because  
igraph.VertexDendrogram expects a matrix that encodes the _merges_  
performed by starting from separated vertices. The format of the merge  
matrix is explained in detail here:

http://cneurocvs.rmki.kfki.hu/igraph/doc/python/igraph.clustering.Dendrogram-class.html

Given a merge matrix, you can form a VertexDendrogram as follows:

d = VertexDendrogram(graph, merges)

Dendrograms are initally cut at the level where the partition produces  
the best modularity, so d.membership returns this partition. d.cut()  
cuts the dendrogram at a different level. plot(d) plots the dendrogram.

You might also be interested in the following recent patch that  
corrects a bug in the Dendrogram object (this will be included in the  
next minor release):

http://cneurocvs.rmki.kfki.hu/cgi-bin/archzoom.cgi/address@hidden/igraph--main--0.6--patch-33/interfaces/python/package/clustering.py.diff?diff

--
Tamas