[Networkit] Load Balanced Clustering Coefficients
michael.hamann at kit.edu
Wed Nov 5 13:05:48 CET 2014
Am Samstag, 1. November 2014, 15:25:57 schrieb Christian Staudt:
> Hi NetworKit algorithm engineers,
> the following work on load-balanced clustering coefficients was pointed out
> to me:
> Any comments? Should we implement this?
There are two main differences between their approach and our current parallel
- They use intersection of (sorted) adjacency lists for triangle counting
instead of using a separate data structure. From their results I have the
impression that their method is faster but we need to confirm that.
- They use static scheduling with a pre-calculation for load-balancing. I'm
not sure that this is a big advantage over dynamic scheduling in practice as
they also get an overhead of 10-20%. However the "balanced" scheduling that we
are currently using doesn't perform well for load-balancing clustering
coefficient calculation, in my experience (mainly on my laptop though) dynamic
scheduling with a block size of 500 gives a much better balance.
More information about the NetworKit