Betweenness Centrality Tractability?

[cookieups]

Running this algo on a directed graph with 30K nodes and 50K Edges is extremely slow. The output during betweennessCentralityMap phase is roughly 1 vertex completed per 3 minutes. I realize that this can be a O(n^3) scale problem depending on algorithm, but this seems prohibitively slow. Running this on a single VM with 10 GB of Memory and 3 cores. Is this behavior normal?

[kbastani]

I agree, this could certainly be improved. I will take a deeper look and see what I can do to improve it.

[cookieups]

Other betweenness centrality programs I've seen that are somewhat efficient have implemented the Brandes "Faster" Algorithm (usually single threaded). On the same set above, it completes in roughly 3 minutes (250 Edges per second), and on a larger set (120K V, 9 MM E) roughly 5 hours (500 Edges per Second) for both Vertex Betweenness Centrality and Edge Betweenness Centrality:

http://algo.uni-konstanz.de/publications/b-fabc-01.pdf