Class DegreePreservingShuffle

Inheritance Relationships

Base Type

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)