Re: [igraph] Slow community detection

[Alexander Struck]

Dear all,

I would appreciate some expectation setting regarding the igraph port of 
Infomap. I have an Infomap process running that works on a directed network of 
1,282,336 nodes and 2,507,034 links. Running time exceeds 100 hours using 
igraph. The C++ implementation from http://mapequation.org/code.html finished 
community detection in 4 min 42 sec on the same machine. My naive expectation 
would have been that any partitioning algorithm that is supposed to run on 
large complex networks is implemented in a fast language and made available to 
igraph using interfaces to these languages. I’m no expert on this and have to 
rely on others to do the actual interfacing work but where went my expectation 
wrong?

Many thanks and best regards,

Alexander

> sessionInfo()
R version 3.2.2 (2015-08-14)
Platform: x86_64-pc-linux-gnu (64-bit)
Running under: Ubuntu precise (12.04.5 LTS)
other attached packages:
[1] igraph_1.0.1


> On 22 Mar 2016, at 22:33, Tamas Nepusz <address@hidden> wrote:
> 
> Hi,
> 
> Analysing a graph of a few million vertices and edges should not be a
> problem for igraph, although not all methods are suited for this. The
> "fast greedy" method and the Louvain method (also known as
> "multilevel" in igraph) probably works fine. InfoMap and walktrap
> might probably take a bit more time. However, note that none of these
> methods (except InfoMap) were explicitly designed for directed graphs,
> so the result might or might not make sense in the end.
> 
> For reference, the "fast greedy" method ran to completion using
> igraph's Python interface in less than two minutes for an Erdos-Renyi
> random network with 1.5 million vertices and 5 million edges, although
> the graph was undirected in this case (because the "fast greedy"
> method does not handle directed graphs anyway).
> 
> So, all in all, I don't think you should be having problems with a
> graph of this size, unless there is something wrong with the R
> interface of igraph (I was trying the Python interface because I'm
> more familiar with that one) or unless Rgui is doing something that it
> shouldn't be doing. If you can upload your graph somewhere, I can try
> and give it a go with R (without the GUI) on a Linux machine.
> 
> T.
> 
> 
> On Tue, Mar 22, 2016 at 1:34 PM, AaaSDFfff <address@hidden> wrote:
>> Hi everyone!
>> 
>> I recently started using the R language and the igraph package. I use these
>> tools to create a directed graph with edge weight attribute containing about
>> 1.2 million vertices and 5 million edges. Creating this kind of graph is
>> easy and really fast. But after I start the community detection on this
>> graph the Rgui always freezes out after about 2 or 3 hours and never returns
>> with the results. The command what I use is this:
>> 
>> clust = groups(cluster_label_prop(g, weights=E(g)$weight)) or clust =
>> cluster_label_prop(g, weights=E(g)$weight)
>> 
>> I tried other comm. det. methods such as walktrap, spinglass or mapinfo but
>> there were the same results. The computer I'm using has:
>> 
>> - win7 64bit
>> - 12 Gbyte RAM
>> - 3.2.3 R 64bit
>> - 1.0.1 igraph
>> 
>> When I use the the mentioned command on a directed graph with edge weight
>> attribute containing about 50.000 vertices and 2 million edges the comm.
>> det. returns with the results after few minutes.
>> 
>> My question is: can somebody gime me an advice about what i should do to
>> make the comm. det. runable and faster?
>> Thx for your answers!
>> 
>> Best regards,
>> Adam
>> 
>> Ps.: Sorry for my english, unfortunatelly I don't have to use it often and
>> I'm not a native speaker
>> 
>> _______________________________________________
>> igraph-help mailing list
>> address@hidden
>> https://lists.nongnu.org/mailman/listinfo/igraph-help
>> 
> 
> _______________________________________________
> igraph-help mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help




Image Knowledge Gestaltung. An Interdisciplinary Laboratory
Cluster of Excellence Humboldt-Universität zu Berlin

Alexander Struck
Data Scientist
Head of IT

Phone: +49 30 2093 66177
E-Mail:  address@hidden
URL:  www.interdisciplinary-laboratory.hu-berlin.de

Street Address: Sophienstrasse 22a, D-10178 Berlin
Postal Address: Unter den Linden 6, D-10099 Berlin

signature.asc
Description: Message signed with OpenPGP using GPGMail