[Networkit] coarsening for ParallelConnectedComponents

Henning Meyerhenke henning.meyerhenke at kit.edu
Tue Jul 18 16:49:58 CEST 2017

Hi Matteo,

The parallel connected components code uses label propagation (LP).
Iterating LP for long would hurt the running time.

If "coarsening" is set to true, after a few LP iterations, the graph is
contracted/coarsened in that clusters become supernodes. The component
search is then continued on the coarse graph recursively.

This should not impact correctness (let me know if you encounter a
problem in that regard). Iirc, we saw decent (albeit not great) speed
improvements for many networks with this scheme over the sequential
BFS-based algorithm in "ConnectedComponents".


Am 18.07.17 um 16:39 schrieb Matteo Riondato:
> Hi all,
> What does the undocumented argument bool coarsening to the ctor of ParallelConnectedComponents do (it defaults to true)?
> What impact does it have on the correctness of the algorithm, if any, and on its runtime?
> Thank you,
> Matteo
> _______________________________________________
> 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 - The Research University in 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: <http://lists.ira.uni-karlsruhe.de/pipermail/networkit/attachments/20170718/fea2af10/attachment.p7s>

More information about the NetworKit mailing list