[Top][All Lists]

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

Re: [igraph] dissimilarity-based community detection

From: Tamas Nepusz
Subject: Re: [igraph] dissimilarity-based community detection
Date: Sat, 22 Mar 2008 22:04:37 +0100

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:


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



reply via email to

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