Class EdgeSwitching¶

Inheritance Relationships¶

Class Documentation¶

class EdgeSwitching : public NetworKit::Algorithm¶

EdgeSwitching and EdgeSwitchingInPlace implement the same algorithm — while the former copies the input graph provided and is more versatile, the in-place implementation only keeps a reference to the input graph.

The Edge

Switching Markov Chain [“The markov chain simulation method for generating connected

power law random graphs”, Mihail and Zegura] perturbates simple directed or undirected graphs while preserving their degrees. In each step, two edges are selected uniformly at random, and their endpoints exchanged. Swaps that introduce multi-edges or self-loops are rejected WITHOUT replacement

—

this is necessary to allow uniform sampling [see “Switching edges to randomize

networks: what goes wrong and how to fix it”, Carstens and Horadam]. The number of successful swaps can be queried using

getNumberOfAffectedEdges()/2.

It’s recommended to implement the preprocessing step in the calling code or to use copying EdgeSwitching implementation.

Note

In general, simple edge switching does not yield a uniform distribution on simple DIRECTED graphs because the orientation of directed triangles cannot be changed. Using DegreePreservingShuffle as a preprocessing step overcomes this limitation. The preprocessing can also jump-start the perturbation process, yielding to potentially faster mixing.

Public Functions

explicit EdgeSwitching(const Graph &G, double numberOfSwitchesPerEdge = 10.0, bool degreePreservingShufflePreprocessing = true)¶

Constructs an EdgeSwitch algorithm that contains a COPY of the input graph.

~EdgeSwitching() override = default¶

inline virtual void run() override¶

Attempts to carry out numberOfSwitchesPerEdge * numberOfEdges() edge swaps (i.e., rejected swaps are counted as well, see Algorithm’s description why)

inline const Graph &getGraph() const¶

Return a reference to the perturbed graph.

inline Graph moveGraph()¶

Move graph owned by the algorithm out.

Warning

Do not call run() after calling moveGraph()

inline count getNumberOfAffectedEdges() const noexcept¶

Returns twice the total number of non-rejected swaps carried out during calls to run(). It hence has the same semantics as Curveball::getNumberOfAffectedEdges().

Note

If run() is called multiple time, the sum over all invocations is returned.

inline double getNumberOfSwitchesPerEdge() const noexcept¶

Return (average) number of switches per edge that will be executed on next run.

inline void setNumberOfSwitchesPerEdge(double x)¶

Modify (average) number of switches per edge that will be executed on next run.