[Networkit] new core decomposition algorithm

Christian Staudt christian.staudt at kit.edu
Sun Oct 4 17:41:52 CEST 2015


I’ve discovered the mistake: The plots showed CPU time, not real time, which made the parallel algorithm look bad. Attached are the new plots. 

I can now confirm that the parallel algorithm is about one order of magnitude faster. It is not game-changing for practical purposes since the sequential implementation was already “fast enough”  (e.g. we go from 10 seconds for a 100M edge graph to 1 second), but still very nice. 


new (parallel)

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

-------------- next part --------------
A non-text attachment was scrubbed...
Name: CoreDecomposition (nk)-time-parallel.pdf
Type: application/pdf
Size: 22563 bytes
Desc: not available
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20151004/511a77a3/attachment-0007.pdf>
-------------- next part --------------

-------------- next part --------------
A non-text attachment was scrubbed...
Name: CoreDecomposition (nk)-eps-parallel.pdf
Type: application/pdf
Size: 23445 bytes
Desc: not available
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20151004/511a77a3/attachment-0008.pdf>
-------------- next part --------------


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

-------------- next part --------------
A non-text attachment was scrubbed...
Name: CoreDecomposition (nk)-eps-seq.pdf
Type: application/pdf
Size: 22633 bytes
Desc: not available
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20151004/511a77a3/attachment-0010.pdf>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: CoreDecomposition (nk)-time-seq.pdf
Type: application/pdf
Size: 22756 bytes
Desc: not available
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20151004/511a77a3/attachment-0011.pdf>
-------------- next part --------------




On 04 Oct 2015, at 16:42, Christian Staudt <christian.staudt at kit.edu> wrote:

> I have a suspicion why my measurements could be wrong. Let me investigate, I’ll report new results when I have a solution.
> Chris
> 
> 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
> 
> _______________________________________________
> 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/511a77a3/attachment-0001.p7s>


More information about the NetworKit mailing list