Class EdgeSwitchingInPlace¶

Inheritance Relationships¶

Class Documentation¶

class EdgeSwitchingInPlace : 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

inline EdgeSwitchingInPlace(Graph &G, double numberOfSwitchesPerEdge = 10.0)¶

Constructs an EdgeSwitch algorithm that will change the input graph IN-PLACE.

Warning

For directed graphs preprocessing with DegreePreservingShuffle is necessary. Either do it manually, or use another constructor.

~EdgeSwitchingInPlace() override = default¶

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)

Note

This function can be called several times. The graph’s topology may not be changed externally between two invocations.

inline Graph &getGraph() const¶

Return a reference to the perturbed graph.

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.

void setNumberOfSwitchesPerEdge(double x)¶

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

Protected Attributes

Graph &graph¶

std::discrete_distribution<node> degreeDistribution¶

Return node x with probability proportional to degree(x)

double numberOfSwitchesPerEdge¶

count numberOfSwapsPerformed = {0}¶