[Top][All Lists]

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

Re: [igraph] dissimilarity-based community detection

From: Kurt J
Subject: Re: [igraph] dissimilarity-based community detection
Date: Sat, 22 Mar 2008 21:20:48 +0000

Great!  Thanks for your help! seems i have some upgrading to do... python2.4->2.5 and igraph0.4.5 -> 0.5

next time I will check the website before posting to the list ;)

On Sat, Mar 22, 2008 at 9:04 PM, Tamas Nepusz <address@hidden> wrote:
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):



igraph-help mailing list

reply via email to

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