Re: [igraph] Slow community detection

[Ádám Sohonyai]

Hi, Tamas!

First of all, thank you for your answer, it is very useful.

After your message I tried to recreate your result so I made two Erdos-Renyi graph (both with 1.2 million vertices and 5.1 million edges) but the first one was directed and the second one was undirected. I made a label_prop clustering on these graphs which method can handle directed graphs as well. In the first case the Rgui freezed out, but in the second case the community detection was done in less than 5 minutes. So, it looks like the comm. det. algorithms can't handle the big directed graphs.

After this I wanted to try this experiment in a Python enviroment and then another problem poped up. In Phyton, after installing the igraph package I tried to import igraph and I got an error message which advised me to use jgraph but in the jgraph package there are no any graph methods or functions.

Do you have any idea what is wrong with the Python igraph package or what I should do to recreate the experiment in Python?

I tried to install igraph from the source provided by Christoph Gohlke but the same happened.

- Phyton version: 3.5.1 Anaconda 2.4.1 (64-bit), MSC v1900 64-bit (AMD-64)

- 16 Gbyte RAM

- win10 64-bit

- Igraph 0.1.11

Thx and best regards,

Adam

2016-03-22 22:33 GMT+01:00 Tamas Nepusz <address@hidden>:

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