Re: [igraph] Slow community detection

[Alexander Struck]

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
>> 
>>

signature.asc
Description: Message signed with OpenPGP using GPGMail