[Networkit] coarsening for ParallelConnectedComponents
henning.meyerhenke at kit.edu
Tue Jul 18 16:49:58 CEST 2017
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,
> NetworKit mailing list
> NetworKit at ira.uni-karlsruhe.de
Karlsruhe Institute of Technology (KIT)
Institute of Theoretical Informatics (ITI)
Prof. Dr. Henning Meyerhenke
Theoret. Informatics / Parallel Computing
KIT - The Research University in the Helmholtz Association
-------------- next part --------------
A non-text attachment was scrubbed...
Size: 5399 bytes
Desc: S/MIME Cryptographic Signature
More information about the NetworKit