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

[David Hunkins]

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