Re: [igraph] dissimilarity-based community detection

[Gabor Csardi]

On Sat, Mar 22, 2008 at 08:47:46PM +0000, Kurt J wrote:
> Thanks Tamas for your quick response.  Two things, however... 
> 
> 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??

The most recent version is 0.5 and it is called 
'python-igraph', see http://pypi.python.org/pypi/python-igraph
or the igraph homepage at igraph.sf.net
The python package requires an installation of the igraph 
C library.

> 2 - I think I mis-represented my intent by poorly framing my question in the
> previous email.  I already have a "dissimilarity" matrix - which is based on
> audio data (independent of network structure) rather than a random walk or
> brownian particle as in Zhou '03.  I am really only interested in the
> "back-half" of the algorithm, using the dissimilarity matrix and a threshold
> value to detect communities...

Yes, community.walktrap is doing exactly this. It starts with a 
(dis)similarity matrix, i.e. a weighted graph, and gives you
the communities. Just like most community structure finding 
algorithms.

Gabor

> I suppose the best option is to implement this using numpy and
> igraph.Clustering() object?
> 
> Cheers,
> Kurt J
> 
> 
> On Sat, Mar 22, 2008 at 8:30 PM, Tamas Nepusz <address@hidden> wrote:
> 
>     Hi,
> 
>     Although I don't know the algorithm you mentioned (I just downloaded
>     the paper from arXiv), my first impression is that the method of
>     Latapy & Pons is similar to that in the sense that it is also based on
>     random walks and it can also take edge weights and directionality into
>     account. The difference is that the method of Latapy & Pons starts
>     from isolated vertices and joins them one by one based on a similar
>     dissimilarity measure and optimizes the modularity of the partition.
>     For their paper, see the following reference:
> 
>     Pascal Pons, Matthieu Latapy: Computing communities in large networks
>     using random walks, http://arxiv.org/abs/physics/0512106
> 
>     This algorithm is implemented in igraph. If you intend to use igraph
>     from C, the corresponding function is igraph_community_walktrap(). The
>     R interface refers to it as walktrap.community, the Python interface
>     calls it Graph.community_walktrap(). In Ruby, it is
>     graph.community_walktrap.
> 
>     Regards,
>     --
>     Tamas
> 
>     On 2008.03.22., at 21:17, Kurt J wrote:
>     > Hi,
>     >
>     > I'm working with audio data and a network of musicians.  I have a n
>     > x n dissimilarity matrix derived from audio analysis and I want to
>     > use it to detect community in the musician friendship network.  The
>     > algorithm described by H. Zhou 2003 (http://prola.aps.org/abstract/PRE/
>     v67/i6/e061901
>     > ) seems a good choice.  Is something like this implemented in igraph?
>     >
>     >
>     > -Kurt J
>     > _______________________________________________
>     > igraph-help mailing list
>     > address@hidden
>     > http://lists.nongnu.org/mailman/listinfo/igraph-help
> 
> 
> 
>     _______________________________________________
>     igraph-help mailing list
>     address@hidden
>     http://lists.nongnu.org/mailman/listinfo/igraph-help
> 
> 

> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help


-- 
Csardi Gabor <address@hidden>    UNIL DGM