Defined in File DegreePreservingShuffle.hpp
public NetworKit::Algorithm
(Class Algorithm)
Implementation of the preprocessing step proposed in “Smaller Universes for Uniform Sampling of 0,1-matrices with fixed row and column sums” by Annabell Berger, Corrie Jacobien Carstens [https://arxiv.org/abs/1803.02624]
The algorithms randomizes a graph without changing its topology simply by renaming nodes. For any degree d (in case of an directed graph it’s a degree pair) consider the set X_d of node ids which have this degree. Then shuffle the ids in X_d.
Hence the algorithm satisfies: For all x in Ginput: i) Ginput.degreeIn(x) = Goutput.degreeIn(x) ii) Ginput.degreeOut(x) = Goutput.degreeOut(x)
The authors argue that applying this preprocessing step before executing (Global)Curveball leads to a faster mixing time.
@node If you want to use it as a preprocessing step to GlobalCurveball, it’s more efficient to set degreePreservingShufflePreprocessing in GlobalCurveball’s constructor.
Public Functions
Instantiate a DegreePreservingShuffle object
G – Input graph that will be shuffled
Execute trades as configured in the constructor. The algorithm is parallel.
Warning
This function has to be called exactly once before invoking getGraph()