timlrx / graph-benchmarks Goto Github PK

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!

I know you said that memory consumption are out of scope of your study, but I am curious about your intuition on this. I am looking for a package that's the most memory efficient. My raw list of edges (in numpy) takes 16 GB, but when creating a networkx instance from the edge list, it requires more than 64GB of memory :(

Hi, I've noticed that the NetworKit shortest-path benchmark is executed with

distance.BFS(g, node_index).run()

However, with this API NetworKit will also store all shortest paths from node_index to all the other nodes, which implies a significant memory and time overhead. This behavior is a bit counterintuitive, and should be better documented, one does not expect BFS to store by default all shortest paths.
Since the other tools only compute the shortest distances, for a fair comparison you should run this:

distance.BFS(g, node_index, storePaths=False).run()

In terms of raw performance networkx.pagerank_scipy can be 4-5X faster than networkx.pagerank. For the google.txt file on my local machine.

In [4]: %%timeit
   ...: nx.pagerank(G, alpha=0.85, tol=1e-3, max_iter=10000000)
   ...:
40.1 s ± 5.19 s per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [5]: %%timeit
   ...: nx.pagerank_scipy(G, alpha=0.85, tol=1e-3, max_iter=10000000)
   ...:
8.89 s ± 48.3 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)```

Hi @timlrx, thanks for the very interesting work. I am trying to run the benchmarks following your instructions but have some troubles running lightgraphs.jl. I am using the LightGraphs master branch as suggested in the file (and also the master branch of graph-benchmarks), but it seems to have different implementations about functions like ShortestPaths and Centrality with the ones expected in lightgraphs.jl. For example, I found LightGraphs.ShortestPaths as LightGraphs.Experimental.ShortestPaths, but could not find ThreadedBFS and Centrality. Could you provide suggestions on which version I should use to run the lightgraphs.jl benchmark? Thanks!

Hi, I read your blog post about benchmarking graph network packages; nice work. Have you run any tests on performance of building out a graph, node by node, or do you know of any? thanks