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

[Tamas Nepusz]

> 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.
The edge betweenness community detections runs a full edge betweenness  
calculation on the whole graph, removes the edge with the highest  
centrality and then re-calculates all betweennesses until no edge  
remains in the network. I don't know how your network actually looks  
like, but I generated an undirected BA graph with 10K nodes and 100K  
edges and tried the EB algorithm on it. Calculating all EBs took 236s.  
This has to be done 100K times, although the number of edges decrease  
with every step. EB calculation is AFAIK linear in the number of  
edges, so I estimated the calculation time for m nodes with m * 236s /  
100K, therefore the whole calculation should take roughly 1.18 * 10^7  
seconds - 136.57 days. This is due to the computational cost of the EB  
calculation.
I'd try other community detection algorithms implemented in igraph  
(e.g., community.fastgreedy, community.walktrap, community.spinglass),  
all of them are likely to yield results of similar quality, but much  
faster.

--
T.