[Networkit] new core decomposition algorithm

Christian Staudt christian.staudt at kit.edu
Sat Oct 3 21:22:23 CEST 2015


On 17 Sep 2015, at 14:51, Henning Meyerhenke <henning.meyerhenke at kit.edu> wrote:

> Some additional measurements on phipute1 show that the new implementation with Max's thread local buffers is clearly faster (a factor of 5 is typical) than the old one.

Well, this is not the picture I get from my recent benchmark on 13 complex networks. It shows (at least as clearly) that the new algorithm is on average slower with a large variance towards the slow side.

See for yourself in the attached plots: Speed is measures in edges per second (dividing the graph size by the running time), averaged over 4 runs and aggregated over the set of graphs.


new (parallel):

-------------- next part --------------
A non-text attachment was scrubbed...
Name: epsSummary.pdf
Type: application/pdf
Size: 15406 bytes
Desc: not available
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20151003/2bc33eb5/attachment-0006.pdf>
-------------- next part --------------

-------------- next part --------------
A non-text attachment was scrubbed...
Name: CoreDecomposition (nk)-eps.pdf
Type: application/pdf
Size: 22530 bytes
Desc: not available
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20151003/2bc33eb5/attachment-0007.pdf>
-------------- next part --------------

-------------- next part --------------
A non-text attachment was scrubbed...
Name: CoreDecomposition (nk)-time.pdf
Type: application/pdf
Size: 21702 bytes
Desc: not available
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20151003/2bc33eb5/attachment-0008.pdf>
-------------- next part --------------


old (sequential): 

-------------- next part --------------
A non-text attachment was scrubbed...
Name: epsSummary-old.pdf
Type: application/pdf
Size: 14174 bytes
Desc: not available
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20151003/2bc33eb5/attachment-0009.pdf>
-------------- next part --------------

-------------- next part --------------
A non-text attachment was scrubbed...
Name: CoreDecomposition (nk)-eps-old.pdf
Type: application/pdf
Size: 21857 bytes
Desc: not available
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20151003/2bc33eb5/attachment-0010.pdf>
-------------- next part --------------

-------------- next part --------------
A non-text attachment was scrubbed...
Name: CoreDecomposition (nk)-time-old.pdf
Type: application/pdf
Size: 21983 bytes
Desc: not available
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20151003/2bc33eb5/attachment-0011.pdf>
-------------- next part --------------

What is going on here? 

Chris



-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 5084 bytes
Desc: not available
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20151003/2bc33eb5/attachment-0001.p7s>


More information about the NetworKit mailing list