[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Tamas Nepusz
Subject: Re: [igraph] Slow running speed of the R igraph lib
Date: Thu, 3 Apr 2008 11:13:28 +0200

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.


reply via email to

[Prev in Thread] Current Thread [Next in Thread]