Class DegreePreservingShuffle¶

Inheritance Relationships¶

Class Documentation¶

class DegreePreservingShuffle : public NetworKit::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

DegreePreservingShuffle() = delete¶

explicit DegreePreservingShuffle(const Graph &G)¶

Instantiate a DegreePreservingShuffle object

Parameters:

G – Input graph that will be shuffled

~DegreePreservingShuffle() override¶

virtual void run() final¶

Execute trades as configured in the constructor. The algorithm is parallel.

Warning

This function has to be called exactly once before invoking getGraph()

Graph getGraph() const¶

Returns a shuffled copy of the input graph.

Warning

Invoke run() before calling this function.

inline const std::vector<node> &getPermutation() const noexcept¶

Returns a reference to the permutation used for shuffling, with permutation[old] = new.

Warning

Invoke run() before calling this function.

Public Static Functions

static inline Graph shuffleGraph(const Graph &input)¶