[Networkit] new core decomposition algorithm

Henning Meyerhenke henning.meyerhenke at kit.edu
Wed Sep 16 20:13:47 CEST 2015


Christian,

Thanks for further benchmarking.

Am 16.09.15 um 18:58 schrieb Christian Staudt:
> It seems to me that the new implementation of core decomposition is
> no improvement. I ran just a few tests on big graphs:
>
> uk-2002 (260 M edges): old: Wall time: 22.7 s new: Wall time: 44 s
>
> eu-2005 (54 M edges) old: Wall time: 13.5 s new: Wall time: 30.1 s
>
> This is bad considering that old version is sequential and the new
> version ran in parallel with 32 threads. Anyone getting different
> results for large graphs (which are those that matter)?
>
> I suggest reverting the changes in the Dev branch and testing the new
> algorithm in a separate branch, until experiments show that it is in
> general faster than the existing implementation.

I reset the default behavior to use the old algorithm.


> ps. By the way, I consider the previous implementation more or less
> fast enough, so a better algorithm is not urgently needed in my
> opinion.

You know why it would be beneficial to have a parallel k-core 
decomposition algorithm. But clearly, it must be found out what hampers 
the ParK implementation (and if this is due to the algorithm or the 
implementation).

Best,
Henning

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 5399 bytes
Desc: S/MIME Cryptographic Signature
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20150916/f3d20758/attachment.p7s>


More information about the NetworKit mailing list