[Networkit] new core decomposition algorithm

Christian Staudt christian.staudt at kit.edu
Sun Oct 4 16:42:46 CEST 2015

I have a suspicion why my measurements could be wrong. Let me investigate, I’ll report new results when I have a solution.

On 03 Oct 2015, at 21:22, Christian Staudt <christian.staudt at kit.edu> wrote:

> 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):
> <epsSummary.pdf>
> <CoreDecomposition (nk)-eps.pdf>
> <CoreDecomposition (nk)-time.pdf>
> old (sequential): 
> <epsSummary-old.pdf>
> <CoreDecomposition (nk)-eps-old.pdf>
> <CoreDecomposition (nk)-time-old.pdf>
> What is going on here? 
> Chris
> _______________________________________________
> NetworKit mailing list
> NetworKit at ira.uni-karlsruhe.de
> https://lists.ira.uni-karlsruhe.de/mailman/listinfo/networkit

-------------- 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/20151004/2b41aecd/attachment.p7s>

More information about the NetworKit mailing list