[Networkit] NetworKit Benchmark

Christian Staudt christian.staudt at kit.edu
Fri Oct 10 09:15:04 CEST 2014

Hi everybody,
I have attached results for the first comprehensive benchmark of NetworKit’s analytics kernels. Speed is measured in edges/s, relating the size of the network to the running time. Most kernels were run multiple time on a set of 14 networks in the size range from 7k to 260M edges. A smaller subset was used for the expensive ones. The box plots illustrate the range of speeds achieved.

- ConnectedComponents and BFS actually do a complete search of the graph and scan all the edges, at a speed of 10^7 - 10^8 edges/s. It seems to me that this is close to the maximum „throughput“ we can get, but let’s see if we can push that further in the future.
- ConnectedComponents is in general very fast, except on one instance with a huge number of components. It is an open problem to see how this can be fixed.
- The iFub diameter algorithm is pretty impressive: It has a worst-case complexity of O(nm), but is in practice orders of magnitudes faster on complex networks than naive calculation of the diameter.
- Approximation of the clustering coefficient is extremely fast since it needs only a constant number of samples.
- Betweenness approximation with an error bound of 0.1 is about 2 orders of magnitude faster than exact calculation - still an expensive algorithm though, due to the nature of the problem.

Any comments or suggestions?



Christian Staudt

christian.staudt at kit.edu
Institute of Theoretical Informatics - Parallel Computing Group 
Building 50.34 Room 034
Karlsruhe Institute of Technology (KIT)

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20141010/5d518e4f/attachment-0002.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: epsSummary.pdf
Type: application/pdf
Size: 97572 bytes
Desc: not available
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20141010/5d518e4f/attachment-0001.pdf>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20141010/5d518e4f/attachment-0003.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 495 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20141010/5d518e4f/attachment-0001.sig>

More information about the NetworKit mailing list