[Networkit] Load Balanced Clustering Coefficients

Michael Hamann 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:
> https://www.researchgate.net/publication/262282519_Load_balanced_clustering_
> coefficients
> 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 mailing list