Re: [igraph] Slow running speed of the R igraph lib

[Gabor Csardi]

Ok, so this is the edge betweenness algorithm. I suggest 
to run just a simple edge betweenness calculation and 
measure the running time:

system.time(eb <- edge.betweenness(mygraph))

and then multiply this by the number of nodes to 
get an estimate for the running time of the edge 
betweenness community structure finding algorithm.
This is only a rought estimate, and it is basically
only an upper limit if the network is sparse.

You can also try to extract a subgraph from your 
graph and see how the algorithm performs on
smaller graphs with the same average degree.

Calculating edge betweenness is an O(mn) operation,
and we need to do this m times, so the community 
structure finding is O(m^2 n). 
Why do you think that it should be faster?

Gabor

On Wed, Apr 02, 2008 at 05:48:13PM -0400, Gang Su wrote:
> Hey network folks,
> 
> I ran into a performance issue, have any of you guys used the 
> edge-betweeness community detection on large datasets? I have run the 
> community detection on a Pentium 4 with 2 G ram, windows XP, with ~10k 
> nodes and 100k edges.  It has been running for 50 hours and still 
> running. According to the original paper, the C version should not be 
> running that long.
> 
> Have anyone analyzed an network of such scale? Any suggestions?
> Thanks!
> 
> Gang Su
> 
> PhD student
> Bioinformatics training track
> Program in Biomedical Sciences
> University of Michigan, Ann Arbor
> MI, 48105, U.S.A.
> 
> 
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help

-- 
Csardi Gabor <address@hidden>    UNIL DGM