[Networkit] new core decomposition algorithm

Henning Meyerhenke henning.meyerhenke at kit.edu
Mon Oct 5 09:48:58 CEST 2015


Thanks for the clarification, Christian!

NB: "Fast enough" is a very relative term and must be seen in the 
context of an application. Simply think of a profile of a massive 
network which includes numerous linear-time kernels. If it requires two 
minutes or 20 minutes for generation does make a difference in someone's 
workflow.


Am 04.10.15 um 17:41 schrieb Christian Staudt:
> 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)
>
>
>
>
>
>
>
>
>
>
>
> old:
>
>
>
>
>
>
>
>
>
>
> 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
>
>
>
> _______________________________________________ NetworKit mailing
> list NetworKit at ira.uni-karlsruhe.de
> https://lists.ira.uni-karlsruhe.de/mailman/listinfo/networkit
>

-- 

=======================================================
Karlsruhe Institute of Technology (KIT)
Institute of Theoretical Informatics (ITI)

Prof. Dr. Henning Meyerhenke
Theoret. Informatics / Parallel Computing

Phone: +49-721-608-41876
Web: http://parco.iti.kit.edu/henningm/

KIT - University of the State of Baden-Wuerttemberg and
National Research Center of the Helmholtz Association
=======================================================


-------------- 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/20151005/9ad97497/attachment.p7s>


More information about the NetworKit mailing list