In order to compare the performances of different libraries, we have collected a dataset of 12 network from the well-known SNAP dataset (http://snap.stanford.edu/data/index.html). In particular, the networks chosen are the following:
As a benchmark of comparison, we have chosen 8 of the most common algorithms in graph theory: computing the diameter, the maximum flow between two vertices, finding connected components, strongly connected components, computing betweenness centrality, the clustering coefficient, the clique number, and generating a graph with the preferential attachment model. We have used "big" networks for linear-time algorithms (computing connected and strongly connected components), and "small" networks for all other algorithms. For the last test, we have generated a graph with 10,000,000 nodes and average degree 4, using the preferential attachment model.
Tests were performed on a Dell
Latitude E6430, Intel Core I7 Quad-Core, 2.7GHz, running Lubuntu 15.04.
The C libraries were compiled with gcc 4.9.1, optimization level 3,
while Python version was 2.7. The results of the comparison are shown in the following table, also available as a Google Sheet: for each library and for each algorithm, we show the number of seconds needed to run the algorithm on all the inputs chosen (missing numbers mean that the algorithm is not implemented). Loading time was not considered, and some computations were stopped, since they needed more than 3 hours.
Unpublished Works > Performance Improvements for the Graph Module of Sagemath > Library Comparison >