Re: [igraph] Slow community detection

[Tamas Nepusz]

Hi Alexander,

The problem here is that igraph contains an _older_ version of the
InfoMap code with a slower implementation. The old implementation was
released under the GNU GPL (if I remember correctly), so we could
simply include it in igraph. The new implementation is licensed under
GNU AGPL, which is incompatible with GNU GPL, meaning that we cannot
include it in igraph unless we re-license igraph under GNU AGPL. (Or,
at least, that's what I was told, but I'm no lawyer).

T.


On Wed, Mar 23, 2016 at 9:22 AM, Alexander Struck
<address@hidden> wrote:
> 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
>
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help
>