Detailed Performance Comparison

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:
  • 3 directed "small" networks: ca-GrQc, p2p-Gnutella08, wiki-Vote;
  • 3 directed "big" networks: cit-Patents, web-Google, wiki-Talk;
  • 3 undirected "small" networks: oregon2_010526, facebook_combined, email-Enron;
  • 3 undirected "big" networks: youtube-u-growth, roadNet-CA, com-youtube.ungraph.

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.

Task
Inputs igraph Boost Networkit Snap Graph-tool Sage
Diameter Undirected small 47.076 130.062 0.042 822.416 696.517 0.293
Maximum flow Undirected small 0.161 6.041

1.595 2.174
Connected components Undirected big 39.446 1.055 0.459 8.583 2.490 11.314
Strong components Directed big >10800.000 0.939 0.876 4.522 2.403 >10800.000
Betweenness centrality Directed small 4.502 3.656 5.474 77.414 11.708 2.493
Clustering coefficient Undirected small 0.076 4.010 0.106 0.952 0.862 10.446
Clique number Undirected small 3195.884



8.874
Preferential attachment 10,000,000 nodes, 2 link/node 15.058
>10800.000 16.536 45.077 >10800.000
Comments