performance question

[merijnpepijndebakker]

Hi,,

Thanks for your work on making IGraph available in Julia!

I currently experiment with large graphs (>2 milion nodes, >4 edges) and work with both Python IGraph and Julia Graphs. I found that for shortest path calculation the Julia Graphs library is typically faster and has the possibility to parallelize. For some other metrics (betweenness centrality) the difference is smaller, although I did not benchmark all this properly.

I'm wondering whether there would be performance gain from using Julia IGraph vs Python IGraph vs Julia Graphs. Can you say something about this? Do you have benchmarks?

Thanks!

[Krastanov]

Hi, @merijnpepijndebakker ! Pardon the slow response!

Most algorithms that are implemented in Julia's Graphs.jl have very competitive performance. If an algorithm is implemented, it will probably be fast (but you should always benchmark it with a graph of representative size for you problem). Julia's Graphs.jl supports some multithreading and distributed computing, but not pervasively. On the other hand, not that many algorithms are implemented in Graphs.jl, so what you need might not exist.

I expect Julia's IGraphs.jl to be exactly as fast as the igraph C library, as Julia has very good foreign function interface capabilities and wraps C code with zero overhead. For most functions I will expect pythons wrapper for igraph to be almost as fast, with some negligible overhead for the size of problems you are working on.

Converting between the datastructure used for representing graphs in IGraphs.jl (a very thin wrapper around the igraph datastructure) and the one used in Graphs.jl is currently very slow (it requires a naive traversal and copy). This can be made much faster in the future, but no one is considering working on this currently. This might or might not be a bottle neck for your work.

Summary: Graphs.jl will be a great option for things that it implements; igraphs and all of its wrappers will be of roughly equal speeds; comparisons between Graphs.jl and igraphs have to be benchmarked for your problem; conversion between Graphs.jl and igraphs is slower than it needs to be.