Re: [igraph] Slow community detection -- Infomap with problems for large graphs?

[Alexander Struck]

Hi Tamas, everyone,

I just want to report, that igraph-R Infomap has still not finished computing 
after 165,657 minutes (16+ weeks). Compared to the same community detection 
done in C++ implementation (4 min) this is a factor of 41414. That makes me 
wonder whether or not the Infomap implementation in igraph may have a problem.
It does seem to work fine for small graphs but does not stop computing in a 
reasonable time for large graphs. Is there a way for me to provide you with 
more detailed information? Should I open an issue somewhere and upload files?

Many thanks for more information and best regards,

Alexander




> On 23 Mar 2016, at 17:33, Alexander Struck <address@hidden> wrote:
> 
> Hi Tamas,
> 
> thank you for your response. I remember the conversation where Gabor brought 
> up the GPL vs AGPL issue. I did not expect changes in this respect. I was 
> rather wondering: Is the older Infomap version implemented in igraph-R using 
> a fast language like C? The run time difference between the old igraph-R 
> implementation (113+ hours) and the latest C++ (4 min) is currently at a 
> factor of about 1700. I wasn’t expecting this performance jump between an 
> older and newer C++ Implementation.
> 
> For the time being I will assume that the older version is implemented in 
> igraph-R using C++. And I will report back if this process ever stops by 
> itself.
> 
> Thanks again,
> 
> Alexander
> 
> 
> 
> 
>> On 23 Mar 2016, at 11:06, Tamas Nepusz <address@hidden> wrote:
>> 
>> 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

signature.asc
Description: Message signed with OpenPGP using GPGMail