search

timlrx / graph-benchmarks

MIT License
79 stars 5 forks source link

Could you include Weighted Betweenness Centrality? #8

Open iandreafc opened 4 years ago

iandreafc commented 4 years ago

I am wondering if we can infer the differences in performance while calculating Weighted Betweenness Centrality from the Shortest Path results you show.

If one algorithm is faster on the shortest path, does this mean it is faster also on betweenness? Does the shortest path algorithm consider arc weights?

It would be great if you could include betweenness (in the version that considers arc weights) in the next benchmarks!

timlrx commented 4 years ago

I think to some extent you can given that the Betweenness involves calculating the shortest path between all pair of vertices of a graph. Though the caveat here is that in the benchmark I measured only the unweighted single source shortest pair as opposed to the weighted all pairs shortest problem. Even so, Lightgraphs should be the fastest due to the threaded shortest path implementation with Graphtool and Networkit taking 2nd place.

Will most definitely consider it the next time I am running the benchmark. Especially adding weights to the shortest path problem.

iandreafc commented 4 years ago

Super, thanks! Can't wait to see how it goes :)