logograph-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 few representative 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=39,796 vertices and E=301,498 edges. The network and test scripts can be downloaded at the bottom of the page.

For this test we used graph-tool 2.33, igraph 0.8.2 and NetworkX 2.4.

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(R) Core(TM) i9-9980HK CPU @ 2.40GHz with 8 cores and 16 threads. In the second column are shown the results for graph-tool with OpenMP enabled using 16 threads, and the third column shows the results using only one thread.

Algorithmgraph-tool (16 threads)graph-tool (1 thread)igraphNetworkX
Single-source shortest path 0.0023 s 0.0022 s 0.0092 s 0.25 s
Global clustering 0.011 s 0.025 s 0.027 s 7.94 s
PageRank 0.0052 s 0.022 s 0.072 s 1.54 s
K-core 0.0033 s 0.0036 s 0.0098 s 0.72 s
Minimum spanning tree 0.0073 s 0.0072 s 0.026 s 0.64 s
Betweenness 102 s (~1.7 mins) 331 s (~5.5 mins) 198 s (vertex)
+ 439 s (edge)
(~ 10.6 mins)
10297 s (vertex)
13913 s (edge)
(~6.7 hours)

When OpenMP is disabled, both graph-tool and igraph seem to deliver an overall comparable performance. However, even in this case graph-tool seems to be faster systematically.

As expected, graph-tool becomes even faster when OpenMP is enabled on algorithms which run in parallel (PageRank, global clustering and betweenness), and thus beats igraph in these cases by a significant margin, which would increase even further for larger networks and machines with more cores.

NetworkX, on the other hand, comes at a distant third with running times in the order of 40 to 250 times slower than graph-tool. This is mostly due to its pure Python implementation, which is known to be in general substantially slower than C/C++ (see here and 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 deciding 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 block model 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, pgp_undirected.xml.gz "The strongly connected component of the PGP network circa 2009."

Graph-tool benchmark script: gt_bench.py

igraph benchmark script: igraph_bench.py

nx benchmark script: nx_bench.py

This page was last updated on 8 July 2020.