logo graph-toolEfficient network analysis

Graph-tool performance comparison

This page shows a succinct performance comparison between graph-tool and two other popular graph libraries with Python bindings, igraph and NetworkX. NetworkX is a pure-python implementation, whereas igraph is implemented in C. Here we select a couple of algorithms which are implemented in all three libraries, and test them on the same graph.

The graph used here is the strongly connected component of the PGP web of trust network circa November 2009. It is a directed graph, with N=39796 vertices and E=301498 edges. The network, test scripts and raw outputs can be downloaded at the bottom of the page.

For this test we used graph-tool version 2.2.23dev, igraph 0.6.4 and NetworkX 1.7.

The functions were called several times, and the average time taken per function call was computed and shown below. All results are for the same Intel Core i7 2620M CPU with 4 cores. In the second column are shown the results for graph-tool with OpenMP enabled using 4 threads, and the third column shows the results using only one core.

Algorithm graph-tool (4 cores) graph-tool (1 core) igraph NetworkX
Single-source shortest path 0.0064 s 0.0063 s 0.012 s 0.127 s
PageRank 0.193 s 0.555 s 0.781 s 34.26 s
K-core 0.0205 s 0.0250 s 0.0181 s 0.9586 s
Minimum spanning tree 0.0268 s 0.0296 s 0.0397 s 0.413 s
Betweenness 579.7 s (~9.6 mins) 1977.6 s (~33 mins) 1182.6 s (~19.7 mins) 53716.692 s (~14.9 hours)

Both graph-tool and igraph seem to deliver overall comparable performance, at least when OpenMP is disabled. In this case, the largest differences above are for PageRank and Betweenness, where igraph is around 1.6x slower in the first but 1.7x times faster in the second.

As expected, graph-tool becomes faster by a factor of 4 when OpenMP is enabled on algorithms which run in parallel (PageRank and Betweenness), and thus beats igraph in these cases by a significant margin, which would increase even further in a machine with more cores.

NetworkX, on the other hand, comes at a distant third with running times in the order of 10 to 170 times slower than graph-tool. This is mostly due to its pure Python implementation, which is known in general to be substantially slower than C/C++ (see here for further comparisons).

One must remember that performance alone is not the only issue which should be considered. All these libraries have their own advantages and disadvantages, which need to be considered in detail when considering what is the best library to use. Here are a couple of important facts:

Additionally, these libraries have different APIs and handle things slightly differently, and they may appeal to different user tastes. Furthermore the set of algorithms which is implemented is not identical. For instance, graph-tool has graph filtering, more extensive flow algorithms, stochastic blockmodel inference, and interactive graph drawing, to name a few unique features. However, both NetworkX and igraph have their own unique features and algorithms which graph-tool currently lacks, and a detailed point-for-point comparison it is out of the scope of this brief analysis. In the end, it is up to the user to make a more detailed comparison and decide what is more appropriate.

Benchmark sources & outputs

Source Network: pgp.xml.gz, "The strongly connected component of the PGP network circa 2009."

Graph-tool benchmark script: gt_bench.py, benchmark outputs: gt_bench.out, gt_bench-single.out

igraph benchmark script: igraph_bench.py, benchmark output: igraph_bench.out

nx benchmark script: nx_bench.py, benchmark output: nx_bench.out