Re: [igraph] betweenness.estimate running very slowly for large graph

[Gábor Csárdi]

David,

betweenness.estimate is quite slow in the 0.5.3 (in fact it is
quadratic), I would suggest to use the (unreleased) 0.6 version for
this. But even this might be too slow for your graph. You can find a
source R package for the latest development snapshot here:
http://code.google.com/p/igraph/downloads/list

Best,
Gabor

On Fri, Apr 30, 2010 at 8:46 AM, David Hunkins <address@hidden> wrote:
> Gabor, Tamas--
> My next issue is that calculating betweenness (or even betweenness.estimate)
> is taking a very long time for my large graph. I took what I thought to be
> the simplest, fastest case, and nothing seems to be happening:
>> summary(g)
> Vertices: 17584663
> Edges: 27831117
> Directed: TRUE
> No graph attributes.
> No vertex attributes.
> Edge attributes: weight.
>> system.time(bw <- betweenness.estimate(g, cutoff=1, verbose=TRUE))
> Betweenness centrali: *-------------------------------------------------|
> [2]+  Stopped                 R
> Timing stopped at: 1720.275 5.374 1785.619
> As you can see I chose the cutoff=1, which is not a result I am interested
> in, but having experience similar long waits with cutoff=5 and cutoff=3, I
> decided to try what should be the fastest run. So the progress meter showed
> no movement in a half-hour, while the processor was maxed at 100% and no
> change at all in memory footprint:
> top - 02:12:12 up  1:07,  3 users,  load average: 0.99, 0.97, 0.89
> Tasks:  56 total,   3 running,  53 sleeping,   0 stopped,   0 zombie
> Cpu(s): 50.0%us,  0.0%sy,  0.0%ni, 50.0%id,  0.0%wa,  0.0%hi,  0.0%si,
>  0.0%st
> Mem:   7872420k total,  6496400k used,  1376020k free,    47304k buffers
> Swap:        0k total,        0k used,        0k free,  1471244k cached
>   PID USER      PR  NI  VIRT  RES  SHR S %CPU %MEM    TIME+  COMMAND
>
> 21396 root      25   0 4779m 4.5g 3260 R  100 60.0  22:25.66 R
>
>     1 root      15   0 10300  800  672 S    0  0.0   0:00.02 init
>
>     2 root      RT   0     0    0    0 S    0  0.0   0:00.00 migration/0
>
>     3 root      34  19     0    0    0 S    0  0.0   0:00.00 ksoftirqd/0
>
>     4 root      RT   0     0    0    0 S    0  0.0   0:00.00 watchdog/0
>
> address@hidden dave]# sar -r 1 10
> Linux 2.6.21.7-2.ec2.v1.2.fc8xen (ip-10-194-207-95)  04/30/10
> 02:13:20    kbmemfree kbmemused  %memused kbbuffers  kbcached kbswpfree
> kbswpused  %swpused  kbswpcad
> 02:13:21      1376004   6496416     82.52     47400   1471244         0
>     0      0.00         0
> 02:13:22      1376004   6496416     82.52     47400   1471244         0
>     0      0.00         0
> 02:13:23      1376004   6496416     82.52     47400   1471244         0
>     0      0.00         0
> 02:13:24      1376004   6496416     82.52     47400   1471244         0
>     0      0.00         0
> 02:13:25      1376004   6496416     82.52     47400   1471244         0
>     0      0.00         0
> 02:13:26      1376004   6496416     82.52     47408   1471236         0
>     0      0.00         0
> I've read that even in 64-bit R implementations some memory structures are
> limited to 2GB. Are there any structures in igraph that are so limited? My
> graph appears to be taking up ~5GB of space in memory.
> Any ideas?
>
> David Hunkins
>
>
>
>
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help
>
>



-- 
Gabor Csardi <address@hidden>     UNIL DGM